题解 | 最大连续子序列

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int k;
	while (cin >> k) {
		if (k == 0)break;
		vector<int> a(k);
		for (int i = 0; i < k; i++)cin >> a[i];
		vector<int> dp(k, 0);
		int res = 0;
		int t = 0, w = k - 1,temp=0;
		bool mark = true;
		dp = a;
		for (int i = 1; i < k; i++) {
			dp[i] = max(dp[i], dp[i - 1] + a[i]);
			//	res=max(res,dp[i]);
			if (res < dp[i]) {
				w = i;
				res = dp[i];	
			}
			if (a[i] == 0&&mark) {
				temp = i;
				mark = false;
			}
			//cout << dp[i] << " ";
		}
		//回溯
		if (res > 0) {
			for (int i = w; i >= 0; i--) {
				if (dp[i] < 0) {
					t = i + 1;
					//cout << t << endl;
					break;
				}
			}
		}
		else if (mark == false) {
			t = temp;
			w = temp;
		}

		if (a.size() == 1)res = a[0] > 0 ? a[0] : 0;
		//if (t > k - 1)t = 0;
		cout << res << " " << a[t] << " " << a[w] << endl;
	}
}