/*

最大連續(xù)子數(shù)組和

給定一個整數(shù)數(shù)組，數(shù)組里可能有正數(shù)、負(fù)數(shù)和零。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。例如，如果輸入的數(shù)組為{1，-2，3，10，-4，7，2，-5}，和最大的子數(shù)組為{3，10，-4，7，2}，那么輸出為該子數(shù)組的和為18.

*/

/*

思路：

? ? 令currsum是當(dāng)前元素結(jié)尾的最大連續(xù)子數(shù)組的和，maxsum是全局的最大子數(shù)組的和，當(dāng)往后掃描時，對第j個元素有兩種選擇，要么放入前面找到的子數(shù)組，要么作為新子數(shù)組的第一個元素：如果currsum>0，則令currsum加上a[j];如果currsum<0，則current(j)為以j結(jié)尾的最大連續(xù)子數(shù)組的和，那么currsum(j)=max{0，currsum[j-1]}+a[j].如果maxsum<currsum，則更新maxsum=currsum:否則maxsum保持原值，不更新。

*/

#include<iostream>

using namespace std;

int main()

{

int array[100],i,n,maxsum,currsum;

cin>>n;

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

cin>>array[i];

currsum=0;

maxsum=array[0];

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

{

if(currsum>=0)

currsum+=array[i];

else

currsum=array[i];

if(currsum>maxsum)

maxsum=currsum;

}

cout<<maxsum<<endl;

return 0;

}