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

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

#include <bits/stdc++.h>

using namespace std;

const int maxn = 60007;
int a[maxn];
int dp[maxn];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    dp[0] = 0;
    for (int i = 1; i <= n; ++i)
        dp[i] = max(dp[i - 1] + a[i],  max(0,a[i]));

    int ans = *max_element(dp, dp + n);
    cout << ans;
    system("pause");
    return 0;

}

My program outputs 187, but i got WA#1. Why?

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

>
>
i found my mistake

Edited by author 20.11.2005 00:44

Why in example 2, such a response?
3 -1 -5 -6
answer 3?

var
p:int64;
i,n,x:integer;
max:int64;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
readln(p);
max:=p;
for i:=1  to n-1 do
  begin
  readln(x);
  if x>=p+x then p:=x else p:=p+x;
  if p>max then max:=p;
  end;
if max<0 then  writeln(0) else writeln(max);
end.

Edited by author 18.11.2009 00:20

Edited by author 18.11.2009 00:21

Edited by author 18.11.2009 00:23

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

the maximum is 31-41+59+26-53+58+97=177 or am I wrong on the way to the right idea? please help

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

Here's the code...

#include<iostream>;
using namespace std;

int main(){
int k=0;
int max=0;
int maxi=0;
int n=0;
 cin >> n;
 for (int i=1;i<=n;i++)
 {
     cin >> k;
     if (max+k < 0)
         max = 0;
     if (max+k > 0)
         max = max + k;
     if (max > maxi)
         maxi = max;
 }
 cout << maxi;
return 0;
}

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

Here is my code:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,max,i,sum,a:integer;

begin
 max:=0;
 sum:=0;
 readln(n);
 for i:=1 to n do
  begin
   readln(a);
   sum:=sum+a;
   if sum>max then
    max:=sum;
  end;
 writeln(max);
end.

I've tested it. It is allright. But i get WA!!!
Why?

The problem is easy, IMHO. I don't understand why so few people have solved it.

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.