写的第一个版本，使用穷举（暴力）的方法，时间复杂度是O(N^2)，执行时间超过限制，代码如下：
1 #include <stdio.h> 2 #define MAX_LEN 100000UL 3 4 int max_subsequence(int *array, unsigned int len, unsigned int *start, unsigned int *end) 5 { 6 int max_val = array[0], sum; 7 int t_start = 0; 8 9 *start = *end = 0; 10 11 while(t_start < len){ 12 sum = 0; 13 for (int i = t_start; i < len; i++){ 14 sum += array[i]; 15 if (sum > max_val){ 16 max_val = sum; 17 *start = t_start; 18 *end = i; 19 } 20 } 21 ++t_start; 22 } 23 24 *start += 1; 25 *end += 1; 26 return max_val; 27 } 28 29 int main(void) 30 { 31 int A[MAX_LEN]; 32 int i = 0, round, n, max; 33 unsigned int start, end; 34 35 scanf("%d", &round); 36 37 while (i++ < round) 38 { 39 scanf("%d", &n); 40 for (int j = 0; j < n; j++){ 41 scanf("%d", &A[j]); 42 } 43 max = max_subsequence(A, n, &start, &end); 44 45 printf("Case %d: ", i); 46 printf("%d %d %d ", max, start, end); 47 } 48 49 return 0; 50 }
接着，我又参考了一篇最大子串的文章，编写了下面的代码，成功AC，代码如下：
1 #include <stdio.h> 2 #define MAX_LEN 100000UL 3 4 int max_subsq(int *array, unsigned int size, unsigned int *start, unsigned int *end) 5 { 6 int max_sum = -2000, sum = 0; 7 int curstart = *start = 0; 8 unsigned int i; 9 10 for (i = 0; i < size; i++){ 11 if (sum < 0){ 12 sum = array[i];//丢弃之前的子串 13 curstart = i; //将当前位置作为新的起始位置 14 } else { 15 sum += array[i]; 16 } 17 18 if (sum > max_sum){ 19 max_sum = sum; 20 *start = curstart; 21 *end = i; 22 } 23 } 24 25 return max_sum; 26 } 27 28 int main(void) 29 { 30 int A[MAX_LEN]; 31 int i = 0, round, n, max; 32 unsigned int start, end; 33 34 scanf("%d", &round); 35 36 while (i++ < round) 37 { 38 scanf("%d", &n); 39 for (int j = 0; j < n; j++){ 40 scanf("%d", &A[j]); 41 } 42 max = max_subsq(A, n, &start, &end); 43 44 printf("Case %d: ", i); 45 printf("%d %d %d ", max, start + 1, end + 1); 46 47 if (i != round) printf(" "); 48 } 49 50 return 0; 51 }
程序的基本思想为：记录前面子序列的和sum，如果和小于0，就丢弃这一段。为什么可以sum<0，就舍弃，重新开始扫描呢？以下证明：
我们用i表示子序列的起始下标，j 表示子序列的终止下标。原理是，当我们得到一个子序列，如果子序列的第一个数是非正数，那么可以舍去
当一个子序列的前n个元素和为非正数时，是否也可以舍去呢？答案是可以的。假设k 是i到j中任意一个下标。Sum( a, b ) 表示子序列第a个元素到第b个元素之和。由于加到第j个元素，子序列才开始为负数，所以Sum( i, k ) > 0，Sum( i, k ) + Sum( k, j ) = Sum( i, j ) ,所以Sum( k, j ) < Sum( i, j ) < 0
所以如果把 k到j的序列附加到j之后的序列上，只会使序列越来越小。所以i到j的序列都可以舍去。
但是，要是所有元素都是负数时，此程序能正确定位最大子序列吗？先构造下面的数据：
然后运行程序，结果如下：
因为每次都是先判断sum是否小于0，然后再添加新的元素，最后将sum与max_sum比较。如果全部为负数就变成了每次保留下来的子序列都只有一个元素（array[i]），这样，就相当于在所有负数中寻找最大值。可见，此算法是可行的。