Обсуждение @ 1146. Maximum Sum @ Timus Online Judge

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

Послано Vokin Andrei (vokin_andrei@mail.ru) 18 фев 2002 21:59

Re: Use DP

Послано Tran Nam Trung (trungduck@yahoo.com) 19 фев 2002 06:54

Re: Use DP

Послано Vokin Andrei (vokin_andrei@mail.ru) 23 фев 2002 01:35

Please, give me any hint.

Re: Use DP

Послано PSV 5 июл 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. (-)

Послано Alexey 10 июл 2006 14:44

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

Послано Anton [SUrSU] 10 июл 2006 16:20

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

Обсуждение задачи 1146. Maximum Sum