Description
给定n(1<=n<=100000)个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。
注意：本题目要求用动态规划法求解，只需要输出最大子段和的值。 Input
第一行输入整数n(1<=n<=100000)，表示整数序列中的数据元素个数；
第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。 Output
输出所求的最大子段和
Sample Input
6
-2 11 -4 13 -5 -2
Output
20
#include <iostream> using namespace std; int main() { ios::sync_with_stdio(false);//不加会超时 cin.tie(0); int a[1000001]; int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; int ans=0; int sum=0; for(int i=0;i<n;i++) { sum+=a[i]; if(sum<0) sum=0; if(sum>ans) ans=sum; } cout<<ans<<endl; return 0; }