题目链接：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）本就是一个非常高效的算法了，所以在测试数据不是很大的情况下，性能上的差距可能不明显，但是如果进一步增大测试数据的数量级，还是能看到性能上的差距的
