Kadane's Algorithm (Finding The Maximum Contiguous Subsequence In A One-Dimensional Sequence)

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

#define siz 1000005

int a[siz];

int main()

{

    int n,x;

    while(scanf("%d",&n)==1){

        if(n==0) break;

        int mx=0;

        for(int i=0;i<n;i++){

            scanf("%d",&x);

            if(i==0) a[i]=(x>0)?x:0;

            else a[i]=((a[i-1]+x)>0)?a[i-1]+x:0;

            mx=max(mx,a[i]);

        }

        printf("%d\n",mx);

    }

    return 0;

}