给出一个整数数组a(正负数都有)，如何找出一个连续子数组（可以一个都不取，那么结果为0），使得其中的和最大？
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
输入
第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
输出
输出最大子段和。
输入示例
6 -2 11 -4 13 -5 -2
输出示例
20
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; __int64 a[50010],dp[50010]; __int64 ans; int main() { int n,i; while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) scanf("%I64d",&a[i]); ans=dp[1]=a[1]; for(i=2;i<=n;i++) { dp[i]=max(dp[i-1]+a[i],a[i]); ans=max(ans,dp[i]); } if(ans<0) printf("%d\n",0); else printf("%I64d\n",ans); } return 0; }