浙大 MOOC 数据结构 01-复杂度2 Maximum Subsequence Sum

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

10
-10 1 2 3 4 -5 -23 3 7 -21

10 1 4

这道题依旧是经典的最大子列和问题，只不过在 浙大 MOOC 数据结构 01-复杂度1 最大子列和问题 的基础上加了要求：“together with the first and the last numbers of the maximum subsequence”和“If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence”，所以需要注意列中全是负数和列中全是负数和0的情况。

#include 
#include 
using namespace std;

#define N 1000000

void MaxSubseqSum(int a[], int n)
{
	int sum = 0, maxSum = -1;//初始化为-1，可以判断列中只有负数和0的情况
	int maxStart=a[0], maxEnd = a[n-1];
	int start=a[0];
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (sum > maxSum)//更新最大子列和的子列
		{
			maxSum = sum;
			maxStart = start;
			maxEnd = a[i];
		}
		else if (sum < 0)//如果当前的子列和小于0，说明后面再加上这个子列不能再使子列和变大，故舍弃该子列
		{
			sum = 0;
			start = a[i + 1];//更新当前子列开始位置
		}
	}
	if (maxSum < 0)//列中全部为负数
		maxSum = 0;
	cout << maxSum << " " << maxStart << " " << maxEnd << endl;
	return;
}

int main()
{
	int n, a[N];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	MaxSubseqSum(a, n);
	return 0;
}