题目链接：https://pintia.cn/problem-sets/434/problems/5404

法一：

 1 int MaxSubseqSum1(int List[], int N)
 2 {
 3     int i, j, k;
 4     int ThisSum, MaxSum = 0;
 5     for (i = 0; i < N; i++)
 6     {
 7         for (j = i; j < N; j++)
 8         {
 9             ThisSum = 0;                //ThisSum是从List[i]到List[j]的子列和
10         
11             for (k = i; k <= j; k++)
12                 ThisSum += List[k];
13             if (ThisSum > MaxSum)
14                 MaxSum = ThisSum;
15         }
16         
17     }
18     return MaxSum;
19 }

这个算法的算法复杂度是O(N^3),是个非常差劲的算法，在pat提交时，提示时间超时，下面是提交结果

法二：

 1 int MaxSubseqSum2(int List[], int N)
 2 {
 3     int i, j;
 4     int ThisSum, MaxSum = 0;
 5     for (i = 0; i < N; i++)
 6     {
 7         ThisSum = 0;                //ThisSum是从List[i]到List[j]的子列和
 8         for (j = i; j < N; j++)
 9         {
10             ThisSum += List[j];
11             if (ThisSum > MaxSum)
12                 MaxSum = ThisSum;
13         }
14     }
15     return MaxSum;
16 }

在法一的基础上进行了改进，将算法复杂度降到了O(N^2),已经比算法一好了很多倍，但是，优秀的程序员在看到一个算法的复杂度是O(N^2)时，都会尝试能不能将它降到O(NlogN）,下面是算法二的提交结果

 

可以看出当测试数据增加到10^6个数量级时，算法是要花费大量时间的。

 

法三：

1 int Max3(int A, int B, int C)
2 {
3     return A > B ? (A > C ? A : C) : (B > C ? B : C);
4 
5 }

利用分治思想

 1 int MaxSum(int List[], int Left, int Right)
 2 {
 3     int MaxLeftSum, MaxRightSum;
 4     int MaxLeftBorderSum, MaxRightBorderSum;    //存放跨越分界线的结果
 5     int LeftBorderSum, RightBorderSum;
 6 
 7     int center, i;
 8     if (Left == Right)
 9     {
10         if (List[Left] > 0) return List[Left];
11         else
12             return 0;
13     }
14     center = (Left + Right) / 2;
15     MaxLeftSum = MaxSum(List, Left, center);
16     MaxRightSum = MaxSum(List, center + 1, Right);
17     LeftBorderSum = 0, MaxLeftBorderSum = 0;
18     for (i = center; i >= Left; i--)
19     {
20         LeftBorderSum += List[i];
21         if (LeftBorderSum > MaxLeftBorderSum)
22             MaxLeftBorderSum = LeftBorderSum;
23     }
24 
25     RightBorderSum = 0; MaxRightBorderSum = 0;
26     for (i = center + 1; i <= Right; i++)
27     {
28         RightBorderSum += List[i];
29         if (RightBorderSum > MaxRightBorderSum)
30             MaxRightBorderSum = RightBorderSum;
31     }
32 
33     //下面返回治的结果
34     return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
35 }

为了和其他算法统一接口，封装一下这个算法，让它和上面两个算法有相同的参数列表接口

1 int MaxSubseqSum3(int List[], int n)
2 {
3     return MaxSum(List, 0, n - 1);
4 }

这个算法的复杂度是O(NlogN)，在上一个算法的性能上又进行了极大的优化，下面是提交结果：

可以看到，但测试数据很大时，算法花费的时间得到了极大的缩减，可以说是一个性能的极大飞跃，但是，还有一个牛到爆炸的算法，不仅算法简短，而且它的算法复杂度是O(N).。这就是传说中的法四

法四：

 1 int MaxSubseqSum4(int List[], int n)
 2 {
 3     int i, ThisSum = 0, MaxSum = 0;
 4     for (i = 0; i < n; i++)
 5     {
 6         ThisSum += List[i];
 7         if (ThisSum > MaxSum)
 8             MaxSum = ThisSum;
 9         else
10         if (ThisSum < 0)
11             ThisSum = 0;
12     }
13 
14     return MaxSum;
15 }

下面是pat提交结果：

虽然从运行时间上看来，这个算法和上一个算法的相差不大（这是因为O(NlogN）本就是一个非常高效的算法了，所以在测试数据不是很大的情况下，性能上的差距可能不明显，但是如果进一步增大测试数据的数量级，还是能看到性能上的差距的