基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注
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
解题思路：简单题。当前加和为负数的时候，就需要开始新的加和，初始状态就是当前的数值。
源代码：
<span style="font-size:18px;">#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<stack> #include<queue> #include<vector> #include<deque> #include<map> #include<set> #include<algorithm> #include<string> #include<iomanip> #include<cstdlib> #include<cmath> #include<sstream> #include<ctime> using namespace std; typedef long long ll; ll ans[50005]; ll dp[50005]; int main() { int N; int i; int flag = 1; scanf("%d",&N); for(i = 1; i <= N; i++) { scanf("%lld",&ans[i]); if(ans[i] >= 0) flag = 0; } dp[0] = 0; for(i = 1; i <= N; i++) { if(dp[i-1]>=0) dp[i] = dp[i-1] + ans[i]; else dp[i] = ans[i]; } sort(dp,dp+N+1); if(!flag) printf("%lld ",dp[N]); else printf("0 "); return 0; } </span>