习题12.2最大连续子序列（浙江大学复试题）

最大连续子序列（浙江大学复试题）

动态规划问题

在最大连续子序列的基础问题上，要求输出子序列的第一个和最后一个数据，且对子序列全部为负数时需进行单独的处理

#include<vector>
using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0)
			return 0;
		vector<int> nums(n), dp(n);
		//1. input data
		bool ifAllMinus = true;
		for (int i = 0; i < n; i++) {
			cin >> nums[i];
			if (nums[i] >= 0)
				ifAllMinus = false;
		}
		//序列中全为负数的处理补丁
		if (ifAllMinus) {
			cout << 0 << " " << nums[0] << " " << nums[n-1] << endl;
			continue;
		}
		//序列中只有一个数字时的处理补丁
		if (n == 1) {
			cout << nums[0] << " " << nums[0] << " " << nums[0] << endl;
			continue;
		}
		//2. 计算最大连续子序列
		int ans_sum = -10e6;
		int ans_left = 0;
		int ans_right = n;
		for (int i = 0; i < n; i++) {
			if (i == 0)
				dp[0] = nums[0];
			else {
				dp[i] = max(dp[i - 1] + nums[i], nums[i]);
				if (dp[i] > ans_sum) {
					ans_sum = dp[i];
					ans_right = i;//最大子序列的右侧节点
					//计算出最大子序列的左侧节点
					int p = i;
					int p_sum = ans_sum;
					for (int j = i; j > 0; j--) {
						p_sum = p_sum - nums[j];						
						if (p_sum == 0) {
							ans_left = p;
							break;
						}
						p--;
					}
				}
			}
		}
		//3. output data
		cout << ans_sum << " " << nums[ans_left] << " " << nums[ans_right] << endl;
	}
	return 0;
}