分析:对于每一个点,考虑将该点数加入到序列构成新的子序列,
还是不加入,开始一段新的子序列。
如果加入得到的子序列和为负,则开始一段新的序列。
如此,可将序列划分成不同的子序列,求其中和的最大值。
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。
输入
第1行:整数序列的长度N(2 <= N <= 50000) 第2 - N + 1行:N个整数(-10^9 <= A[i] <= 10^9)
输出
输出最大子段和。
输入样例
6 -2 11 -4 13 -5 -2
输出样例
20
#include<iostream> #include<algorithm> using namespace std; long long a[50005]; long long dp[50005]; int main() { int n; while(cin>>n){ for(int i=1;i<=n;i++){ cin>>a[i]; dp[i]=0; } long long Max=0; dp[0]=0; for(int i=1;i<=n;i++){ dp[i]=max(dp[i-1]+a[i],(long long)0); Max=max(Max,dp[i]); } cout<<Max<<endl; } return 0; }