PAT 1007 Maximum Subsequence Sum

  1. 1. Maximum Subsequence Sum

Maximum Subsequence Sum

Given a sequence of K integers { N​1​​, N​2​​, …, N​K​​ }. A continuous subsequence is defined to be { N​i​​, N​i+1​​, …, N​j​​ } 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.

Input Specification

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.

Output Specification

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.

Sample Input

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

Sample Output

1
10 1 4

分数线死活不出来，一为排解焦虑，二为准备复试，建了个小号重刷PAT。最大子列和这个问题自己想不出来，听别人的想法似懂非懂，抄的代码放久了还是看不懂，让我头疼不已。今天在往常的思路上多想了一步，迎刃而解。记录一番，以示庆祝。

根据历次的印象，应该用动规。根据历次的印象，应该用前一段的最大子列和与当前元素作为状态转换方程的参数。好了，到了这一步就卡住了。

以往我的思路是，新的子列和=旧子列和+最后一项。旧子列和和最后一项可正可负，但只要最后一项是正的，那么子列和就严格递增。可是这样的思路在后面是-2,5的时候就行不通了。以前走到这一步我就去求助搜索引擎了。

这次在上面的思路上稍微走了一步。加法是有交换律的。不妨把式子改写成新的子列和=最后一项+旧子列和。不考虑最后一项的正负，而去考虑旧子列和的正负。

  • 如果旧子列和为正，那么不管最后一项符号如何，新子列和一定比最后一项要大。
  • 如果旧子列和为负，那么不管最后一项符号如何，新子列和一定比最后一项要小。

如果一个新子列和比最后一项还要小，取仅含最后一项的子序列，则它比新子列和还要大。这时的新子列和并不是最大子列和。舍弃之。

把最后一项当作子列的第一项，重复上述的过程，则可以得到几个连续序列的正数和。最大子列和就藏在这些正数和当中。问题转化求几个数的最大值。这还用想？😛

针对这道题的要求改一改，就得到答案啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
	int k;
	cin >> k;
	vector<int> v = vector<int>(k);
	for (int i = 0; i < k; i++) scanf("%d", &v[i]);
	int i=0, sum = 0;
	int max = -1;
	sum = 0;
	int p = 0, q = k-1;
	int s = 0;
	for(int i=0;i<k;i++)
	{
		sum += v[i];
		if (sum>max)
		{
			max = sum;
			p = s;
			q = i;
		}
		if (sum<0)
		{
			s = i+1;
			sum = 0;
		}
	}
	if (max < 0) max = 0;
	printf("%d %d %d", max, v[p], v[q]);
	return 0;
}

PAT
prev： next：