题目

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 \le i \le j \le 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$ ( $\le 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

思路

可以说是经典算法题目之一了，时间复杂度从O(N^3)到O(N)的算法都存在，编程珠玑、算法导论、数据结构和算法分析（C语言描述）这些书里都有谈到。

当然了这些书里的算法只管计算最大子列和（确实这样就太简单了），并没有记录相应头尾元素，还有什么全是负数还要输出整个数列首位元素（这就是为了出题而出题嘛）。但是程序的骨架是不变的。

O(N)复杂度的算法思路是：记录当前非负子列和和目前最大子列和，若前者变成了负数，便将其重置，直到遍历整个数组。这道题有一个要求：

In case that the maximum subsequence is not unique, output the one with the smallest indices i and j

需要索引最小的子列，这就要在判断条件上有精细的控制。要使得开头索引最小，就要将之前可能存在子列和为0的包含进来，而结尾索引也要最小，就要将之后可能存在子列和为0的排除，如： 2 -2 3 4 -5 5 要选取前4个，而不能包括后2个。

代码

Github最新代码，欢迎交流

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

#include <stdio.h>

int main()
{
	int K, n, first = 0;
	int start, end, sum = -1;   /* the current non-negative subsequence */
	int a = -1, b, s = 0;       /* the maximum-sum subsequence */

	scanf("%d", &K);
	for (int i = 0; i < K; i++) {
		scanf("%d", &n);
		if (i == 0) first = n;               /* record the first number */

		/* update start, end and sum for the current non-negative subsequence */
		if (sum < 0) start = n, sum = 0;     /* reset if sum < 0 */
		sum += n;                           /* update sum */
		if (sum >= 0) end = n;               /* update end if sum >= 0 */

		/* update a, b and s for the so-far maximum-sum subsequence */
		if (sum > s || (!sum && !s))         /* special case is max-sum is 0 */
			a = start, b = end, s = sum;
	}
	/* a won't be updated if all the numbers are negative */
	if (a == -1)
		printf("0 %d %d", first, n);
	else
		printf("%d %d %d", s, a, b);

	return 0;
}