最大的子序列和的问题:

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

 

上一篇:动态规划——NC19. 子数组的最大累加和问题


下一篇:布尔矩阵