Discussion @ 1146. Maximum Sum @ Timus Online Judge

there is a solution with almost O(n)

Posted by maxi 17 Feb 2015 12:34

#include <iostream>
using namespace std;
int n,A[1002],i,maxi,S[1002],st,dr,rez;
int main()
{   cin>>n;
    for(i=1;i<=n;i++)
        cin>>A[i];
    S[1]=A[1];
    for(i=1;i<=n;i++)
        if(S[i-1]<=0)
            S[i]=A[i];
        else
            S[i]=A[i]+S[i-1];
    rez=-1000000;
    for(i=1;i<=n;i++)
        if(S[i]>rez)
            rez=S[i];
    cout<<rez;
    return 0;
}

Re: there is a solution with almost O(n)

Posted by organmusic 29 Apr 2015 20:50

it's just a joke, isn't it?

Discussion of Problem 1146. Maximum Sum