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

Re: Use DP

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. (-)

You must easily find maximum sum in vector for O(n),

only fixed two parameters of submatrix(e.g. top && bottom).