По условию, при входных n = 1 и единственном отрицательном значении ответ должен быть 0, но accepted получается и при неправильном решении такого теста...

Либо я чего-то не понимаю...

Hi guys, any ideas on test #4? getting WA there

Note, the required algorithm is known as the Kadane's algorithm and runs in O(n).

Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память?

I can't understand why. Can anybody help me?

>
>
i found my mistake

Edited by author 20.11.2005 00:44

calculate : fmax(n) = max(fmax(n-1)+value(n),value(n));

Best solution - 0.015.
How to improve?
I do not use array. Only 5 vars - (3 integer and 2 longint)
I use inc([longint], number) instead of [longint]:= [longint] + number;

No more question. I read the text badly.

Edited by author 23.03.2009 03:56

Hi,

Well, the only thing to keep in mind for this problem is that final answer cannot be negative. If it comes to negative then output 0. Secondly, just start adding the numbers from the beginning and keep track of the maximum sum. For example, if you add first three terms and sum comes to 500 and then the fourth term is -500, then don't loose the previous 500 sum. Keep it somewhere, but make your new sum 0. Then start adding from 5th term (0 + 5th term + ....). Whenever you add just check whether the new one is greater than 500 or not ? If it is then replace it with that.

Varun

Edited by author 05.05.2009 11:30

Edited by author 05.05.2009 11:31

time 0.046
memory 906 КБ (wow!!!)

O(N) = (N * log N)

  Is there a faster solution that the one with 3 for's. I would apreciate if there is one.

This is finding maxinmum sum in p array... I have TLE on test #13... Help...

procedure solve;
var
  i,j:longint;
begin
  a[1]:=p[1];
  max:=a[1];
  for i:=2 to n do begin
    a[i]:=p[i]+a[i-1];
    if max<a[i] then max:=a[i];
  end;
  for i:=1 to n do
    for j:=i to n do
      if max<a[j]-a[i]+p[i] then max:=a[j]-a[i]+p[i];
end;

For example:
If N=3
   and p1=3; p2=-3; p3=10; What i and j = ?

Can anybody answer my question? May numbers i and j be equal during the jump and what shall we do if n=0?