题解 | #最大序列和#

#include<iostream>
using namespace std;

const int maxn=1000001;
long long N[maxn];
long long dp[maxn];

long long getmaxdp(int n){
	dp[0]=N[0];
	int i=1;
	while(i<n){
		if(dp[i-1]>0){
			dp[i]=dp[i-1]+N[i];
		}else{
			dp[i]=N[i];
		}
		i++;
	}
	long long answer=dp[0];
	for(int i=0;i<n;i++){
		if(dp[i]>answer){
			answer=dp[i];
		}
	}
	return answer;
}

int main(){
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>N[i];
		}
		cout<<getmaxdp(n)<<endl;
	}
}