题解 | #最大序列和#

经典dp思想
#include<iostream>
#include<climits>
using namespace std;
#define N 1000000
long long a[N];
long long dp[N];   //每一个di[i]要包括a[i]在内，才能保证后续的dp[i]可以连上

long long maxsubsequence(int n) {
	long long res = -INT_MAX;
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			dp[i] = a[i];
		}
		else {
			dp[i] = max(a[i], dp[i - 1] + a[i]);
		}
		if (dp[i] > res) {
			res = dp[i];
		}
	}
	return res;
}

int main() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		long long answer = maxsubsequence(n);
		cout << answer << endl;
	}
}