题解 | #最大序列和#

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = 1e7 + 10;

long long arr[MAXN];

long long dp[MAXN];  //记忆化数组，存储子问题的解

long long getMaxSum(int n){
	long long answer = 0;
	for(int i = 0; i < n; ++i){
		if(i == 0){
			dp[i] = arr[i];
		}else{
			dp[i] = max(arr[i],dp[i - 1] + arr[i]);
		}
		answer = max(answer,dp[i]);
	}
	return answer;
}

int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		for(int i = 0; i < n; ++i){
			scanf("%lld",&arr[i]);
		}
		long long answer = getMaxSum(n);
		printf("%lld\n",answer);
	}
	return 0;
}