N个整数组成的序列a[1],a[2],a[3],…,a[n]，
求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
Input
第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
Output
输出最大子段和。
Input 示例
6 -2 11 -4 13 -5 -2
Output 示例
20
// 1.穷举50000显然超时，时间复杂度为O(n^2).
#include<iostream>
#include<cstdio>
using namespace std;
int a[50005];
int main()
{
int i,j,n;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%d",a+i);
__int64 max=0;
for(i=0;i<n;i++)
{
__int64 sum=0;
for(j=i;j<n;j++)
{
sum+=a[j];
if(sum>max)
max=sum;
}
}
printf("%I64d\n",max);
}
return 0;
}
/* 2.分治法 时间复杂度为O(nlogn).
求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间[start, end]只可能有以下三种可能性:
在[1, n/2]这个区域内
在[n/2+1, n]这个区域内
起点位于[1,n/2],终点位于[n/2+1,n]内
以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理.
第三种情形必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路求出:
以n/2为终点，往左移动扩张，求出和最大的一个left_max
以n/2+1为起点，往右移动扩张，求出和最大的一个right_max
left_max+right_max是第三种情况可能的最大值
*/
#include<iostream>
#include<cstdio>
using namespace std;
int a[50005];
__int64 maxInterval(int *a,int l,int r)
{
if(l==r)
return a[l]>0?a[l]:0;
int mid=(l+r)/2;
__int64 leftmaxInterval=maxInterval(a,l,mid);
__int64 rightmaxInterval=maxInterval(a,mid+1,r);
int i;
__int64 sum=0;
__int64 left_max=0;
for(i=mid;i>=l;i--)
{
sum+=a[i];
if(sum>left_max)
left_max=sum;
}
sum=0;
__int64 right_max=0;
for(i=mid+1;i<=r;i++)
{
sum+=a[i];
if(sum>right_max)
right_max=sum;
}
__int64 ans=left_max+right_max;
if(leftmaxInterval>ans)
ans=leftmaxInterval;
if(rightmaxInterval>ans)
ans=rightmaxInterval;
return ans;
}
int main()
{
int i,j,n;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%d",a+i);
printf("%I64d\n",maxInterval(a,0,n-1));
}
return 0;
}
/* 3.动态规划法 计算时间复杂度为O(n),是最优的解
令b[j]表示以位置 j 为终点的所有子区间中和最大的一个
子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中
如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含
如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[50005];
__int64 b[50006];
int main()
{
// freopen("1.txt","r",stdin);
__int64 max;
int i,n,flag;
while(~scanf("%d",&n))
{
flag=0;
max=0;
for(i=1; i<=n; i++)
{
scanf("%d",a+i);
if(a[i]>0)
flag=1;
}
memset(b,0,n+1);
for(i=1; i<=n; ++i)
{
if(b[i-1]>0)
b[i]=b[i-1]+a[i];
else
b[i]=a[i];
if(b[i]>max)
max=b[i];
}
if(flag)
printf("%I64d\n",max);
else
puts("0");
}
return 0;
}
