题解 | #最大序列和#

关键公式dp[i]=max(dp[i-1]+list[i], list[i])表示至少包含i在内的和最大的子式。

#include <bits/stdc++.h>
using namespace std;
// dp[i][j]=dp[0][j]-dp[0][i];
int main() {
	int N;
	// 1~i存数据
	vector<long long> list;
	// dp[i]:1~i求和。
	vector<long long> dp;
	while(cin>> N) {
		list.clear();
		dp.clear();
		list.push_back(0);
		dp.push_back(0);
		// 输入 
		long long temp;
		for(int i=0; i<N; i++) {
			cin>> temp;
			list.push_back(temp);
		}
        // 选择前i项和或list[i]
        long long res=list[1];
		for(int i=1; i<=N; i++) {
			dp.push_back(max(dp[i-1]+list[i], list[i]));
            res=max(res, dp[i]);
		}
		cout<< res<< endl;
	}
}
// 64 位输出请用 printf("%lld")