Discussion @ 1146. Maximum Sum @ Timus Online Judge

Vokin Andrei (vokin_andrei@mail.ru) Please, help me to solve this problem.Give me a hint. [5] // Problem 1146. Maximum Sum 18 Feb 2002 21:59

Tran Nam Trung (trungduck@yahoo.com) Re: Use DP [4] // Problem 1146. Maximum Sum 19 Feb 2002 06:54

Vokin Andrei (vokin_andrei@mail.ru) Re: Use DP [3] // Problem 1146. Maximum Sum 23 Feb 2002 01:35

Please, give me any hint.

PSV Re: Use DP [2] // Problem 1146. Maximum Sum 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

Alexey Can U describe me O(n^3) solution? I have AC with O(n^4). Thanks. (-) [1] // Problem 1146. Maximum Sum 10 Jul 2006 14:44

Anton [SUrSU] Re: Can U describe me O(n^3) solution? I have AC with O(n^4). Thanks. (-) // Problem 1146. Maximum Sum 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