Discussion @ 1146. Maximum Sum @ Timus Online Judge

How do you get 0.03 s? Less than O(N^4)

Posted by Alyosha Popovich 5 Mar 2002 12:43

Can you solve this problem in less time than O(N^4) ?
please email to scythe@toughguy.net
thank you

do you know...

an O(N) algorithm to solve this task : find the consecutive
subsequence with the largest sum of a given sequence of N integers ?

thank you xyz! your hint really inspires me

Posted by MadPsyentist/Sam 6 Mar 2002 09:56

> an O(N) algorithm to solve this task : find the consecutive
> subsequence with the largest sum of a given sequence of N integers ?

Re: How do you get 0.03 s? Less than O(N^4)

Posted by Dinu Adrian Florin 11 May 2004 13:38

you precalculate sums in the matrix for O(n^3) and uses a DP
to reach O(n^2). I'll send my source later.

Discussion of Problem 1146. Maximum Sum