这是一道很正常的动态规划类题目，从“子序列”就能够想到我们的“最长不下降序列”，在本题中，与我们“最长不下降序列”的不同之处就在于状态不同；

本题中的状态我们可以看作是以第i个数结尾的最大子序列和，即：用f[i]表示以第i个数结尾的最大子序列和；

那么就是状态转移方程了！下面我们来考虑有几种选择吧！

对于第i个数（1<i<=n）来说，有两种选择：

方案1.和第i-1个数构成一个序列

方案2.第i个数单独构成一个序列

很显然，这道题符合无后效性原则，因此我们可以采用动态规划解题；

那么怎样作出选择呢？

显然： 当f[i-1]>0,即f[i-1]+a[i]>a[i]时，选择方案1；

当f[i-1]<=0,即f[i-1]+a[i]<=a[i]时，选择方案2

因此状态转移方程就很容易得出来了！

f[i]=max{f[i-1]+a[i],a[i]}（1<i<=n）

边界：f[1]=a[1]

最终只要f[1...i]中找出最大值就是我们需要的结果啦！

下面就是我的代码啦

using namespace std;
int n,a[10000010],f[10000010],ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
//状态转移方程:f[i]=max(f[i],f[i-1]+a[i])
//本题的状态f[i]：前i个数的最大子序列和
//边界条件：f[i]=a[i]
f[1]=a[1];
for (int i=2;i<=n;i++)
{
f[i]=f[i-1]>0?f[i-1]+a[i]:a[i];//状态转移方程
ans=f[i]>ans?f[i]:ans;//更新最大值
}
printf("%d",ans);
return 0;
}

蒟蒻的第一篇题解！感谢支持！~(≧▽≦)/~

一定要用scanf来输入！ 在10000000数据的输入下scanf比cin要快至少10s（应该要多的多但是网站超过1s会停止编译） 我的程序为

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i,n,max1=-1,a,num=0;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		if(a>0&&num>=0) num+=a;
		else
		if(a<0&&num>=0)
		{
			max1=max(num,max1);
			num=max(0,num+a);
		}//如果算上他会变负则舍弃他与他之前的所有数（num变0）
	}
	cout<<max1;
}