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

How do you get 0.03 s? Less than O(N^4) Alyosha Popovich 5 мар 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... I have answers to all your questions :) 5 мар 2002 22:44

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

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

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.

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