题解 | #最大连续子序列#

与KY22 最大序列和的思想类似，只不过在比较时加上记录首尾元素位置

```#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int maxn = 1000000;
long long dp[maxn];		//用来存储前i个元素的最大子序列
long long arr[maxn];

int fir = 0;			//全局变量用来记录每组数据最大子序列的首位元素
int las = 0;

long long  Max(int n) {
	fir = 0;			
	las = 0;
	int begin = 0;
	int end = 0;		
	dp[0] = arr[0];				//对每组数据都初始化
	long long ans = arr[0];

	for (int i = 1; i < n; i++) {
		if (arr[i] > dp[i - 1] + arr[i]) {
			end = i;								//如果当前元素大于前面子序列 ，则将首尾均置位
			begin = i;
		}
		else {
			end = i;								//否则仅将尾部置位
		}
		dp[i] = max(arr[i], dp[i - 1] + arr[i]);	//存储前i个元素的最大子序列值

		if (ans < dp[i]) {							//若最大和小于dp[i]，将最大和调整为dp[i]，首尾元素也重置
			fir = begin;
			las = end;
			ans = dp[i];
		}
	}
	return ans;

}

int main() {
	int n;
	
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		bool flag = true;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			if (arr[i] >= 0) {					//判断输入元素是否全部为负数
				flag = false;
			}
		}
		if (flag) {
			cout << "0 " << arr[0] << " " << arr[n - 1] << endl;
		}
		else {
			cout << Max(n) << " ";
			cout << arr[fir] << " " << arr[las] << endl;
		}
	}

	system("pause");
	return 0;
}