最大连续子数组和

/*

最大连续子数组和

给定一个整数数组，数组里可能有正数、负数和零。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。例如，如果输入的数组为{1，-2，3，10，-4，7，2，-5}，和最大的子数组为{3，10，-4，7，2}，那么输出为该子数组的和为18.

*/

/*

思路：

    令currsum是当前元素结尾的最大连续子数组的和，maxsum是全局的最大子数组的和，当往后扫描时，对第j个元素有两种选择，要么放入前面找到的子数组，要么作为新子数组的第一个元素：如果currsum>0，则令currsum加上a[j];如果currsum<0，则current(j)为以j结尾的最大连续子数组的和，那么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;

}