题解 | 最大序列和

题目链接

思路：用动态规划，dp[i]表示前i个元素的最大序列和，如果前面累加的和为负数或0，则不计入当前元素前缀最大和；否则加入；

#include<stdio.h>
#include<algorithm>
using namespace std;

long long s[1000001];//存含n个元素的序列
long long dp[1000002];//元素的取值范围 [−10^9,10^9],设成全局变量
int main() {
	int n;//范围1<=n<=10^6
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &s[i]);
	}
	dp[1] = s[0];
	long long maxcnt = dp[1];
	for (int i = 2; i <= n; i++) {
		if (dp[i - 1] <= 0) {
			dp[i] = s[i - 1];//等于第i个元素
		}
		else {
			dp[i] = dp[i - 1] + s[i - 1];//前i-1个元素的最大序列和+第i个元素
		}
		maxcnt = max(dp[i], maxcnt);//更新最大
	}
	printf("%lld\n", maxcnt);
	return 0;
}