Discussion @ 1146. Maximum Sum @ Timus Online Judge

Please, help me to solve this problem.Give me a hint.

Posted by Vokin Andrei (vokin_andrei@mail.ru) 18 Feb 2002 21:59

Re: Use DP

Posted by Tran Nam Trung (trungduck@yahoo.com) 19 Feb 2002 06:54

Re: Use DP

Posted by Vokin Andrei (vokin_andrei@mail.ru) 23 Feb 2002 01:35

Please, give me any hint.

Re: Use DP

Posted by PSV 5 Jul 2006 06:20

Take an array 1..max, 1..max of longint that i,j element includes sum of numbers in 1..i 1..j rectangle - that you can calculate easily by n*n (I hope) than in n^4 cmplesity take all variants of different rectangles and calc their sum
in linear time. I think my English take success with your mind

Can U describe me O(n^3) solution? I have AC with O(n^4). Thanks. (-)

Posted by Alexey 10 Jul 2006 14:44

Re: Can U describe me O(n^3) solution? I have AC with O(n^4). Thanks. (-)

Posted by Anton [SUrSU] 10 Jul 2006 16:20

You must easily find maximum sum in vector for O(n),
only fixed two parameters of submatrix(e.g. top && bottom).

Discussion of Problem 1146. Maximum Sum