题目描述
给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。
输入描述:
第一行为一个正整数N，第二行为N个整数，表示序列中的数。
输出描述:
输入可能包括多组数据，对于每一组输入数据，
仅输出一个数，表示最大序列和。
输入
5
1 5 -3 2 4
6
1 -2 3 4 -10 6
4
-3 -1 -2 -5
输出
9
7
-1
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000000;
int dp[MAXN];//dp[i]表示以第i个元素为末尾的连续序列的最大和,只有两种情况，一个或多个
int a[MAXN];
int maxSub(int n){
int Max=0;
for(int i=0;i<n;i++){
if(i==0) dp[i]=a[i];//初始
else dp[i]=max(dp[i-1]+a[i],a[i]);//多个vs一个
if(dp[i]>Max) Max=dp[i];
}
return Max;
}
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<maxSub(n)<<endl;
}
}