HDOJ(1003) Max Sum

写的第一个版本，使用穷举（暴力）的方法，时间复杂度是O(N^2)，执行时间超过限制，代码如下：

 #include <stdio.h>
 #define  MAX_LEN  100000UL int max_subsequence(int *array, unsigned int len, unsigned int *start, unsigned int *end)
 {
     int max_val = array[], sum;
     int t_start = ;     *start = *end = ;     while(t_start < len){
         sum = ;
         for (int i = t_start; i < len; i++){
             sum += array[i];
             if (sum > max_val){
                 max_val = sum;
                 *start = t_start;
                 *end   = i;
             }
         }
         ++t_start;
     }     *start += ;
     *end   += ;
     return max_val;
 } int main(void)
 {
     int A[MAX_LEN];
     int i = , round, n, max;
     unsigned int start, end;     scanf("%d", &round);     while (i++ < round)
     {
         scanf("%d", &n);
         for (int j = ; j < n; j++){
             scanf("%d", &A[j]);
         }
         max = max_subsequence(A, n, &start, &end);         printf("Case %d:\n", i);
         printf("%d %d %d\n\n", max, start, end);
     }     return ;
 }

接着，我又参考了一篇最大子串的文章，编写了下面的代码，成功AC，代码如下：

 #include <stdio.h>
 #define  MAX_LEN  100000UL int max_subsq(int *array, unsigned int size, unsigned int *start, unsigned int *end)
 {
     int max_sum = -, sum = ;
     int curstart = *start = ;
     unsigned int i;     for (i = ; i < size; i++){
         if (sum < ){
             sum = array[i];//丢弃之前的子串
             curstart = i;  //将当前位置作为新的起始位置
         } else {
             sum += array[i];
         }         if (sum > max_sum){
             max_sum = sum;
             *start = curstart;
             *end   = i;
         }
     }     return max_sum;
 } int main(void)
 {
     int A[MAX_LEN];
     int i = , round, n, max;
     unsigned int start, end;     scanf("%d", &round);     while (i++ < round)
     {
         scanf("%d", &n);
         for (int j = ; j < n; j++){
             scanf("%d", &A[j]);
         }
         max = max_subsq(A, n, &start, &end);         printf("Case %d:\n", i);
         printf("%d %d %d\n", max, start + , end + );         if (i != round) printf("\n");
     }     return ;
 }

程序的基本思想为：记录前面子序列的和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的序列都可以舍去。

但是，要是所有元素都是负数时，此程序能正确定位最大子序列吗？先构造下面的数据：