最大子列和问题

今天来讨论一个很基础的算法问题,数列的最大子列和问题。这道题我是在看浙大陈姥姥的Mooc的时候看到的,算是陈越老师作为算法与数据结构开篇讲解的第一道算法实例题。

那么今天我就来记录一下分析这道题的过程。

常用方法

首先,最大子列和这个问题有一个众所周知的办法,即为每次从数列的开头i,往结尾N累加,当加至结尾时,由i+1再次累加,直到N-N。这样的算法用三个变量三层循环来分别代表从头至尾的遍历,以及从i - N的前进继续累加,最后一层是累加的和。算法可以写成下面这样:

    public static int MaxSubseqSum1(int[] A, int N) {
        int ThisSum, MaxSum = 0;
        int i, j, k;
        for (i = 0; i < N; i++) {
            for (j = i; j < N; j++) {
                ThisSum = 0;
                for (k = i; k <= j; k++) {
                    ThisSum += A[k];
                }
                if (ThisSum > MaxSum) {
                    MaxSum = ThisSum;
                }
            }
        }
        return MaxSum;
    }

上面的第一种方法应该非常好理解,而由于是三层循环,所以,这个算法的时间复杂度是T(N) = O(N^3)。这种时间复杂度的算法,是非常的低效的,并且我们作为一个有追求的程序员,看到一个时间复杂度上有平方以上指数的,必须要考虑的是降次。

那么其实,第一种算法,如果我们仔细思考,那么可以发现它最里面的一层,k循环是一个很愚蠢的行为,因为我们可以直接在第二层循环里完成累加,于是,我们可以写一个稍微简单的算法。

    public static int MaxSubseqSum2(int[] A, int N) {
        int ThisSum;
        int MaxSum = 0;
        int i, j;
        for (i = 0; i < N; i++) {
            ThisSum = 0;
            for (j = i; j < N; j++) {
                ThisSum += A[j];
                if (ThisSum > MaxSum) {
                    MaxSum = ThisSum;
                }
            }
        }
        return MaxSum;
    }

而这个去了一个循环的算法,时间复杂度也一目了然,T(N) = O(N^2),但是时间复杂度依旧还有2次方。接下来还有什么更好的办法么?

分治法

在这里我们介绍一种方法叫分治法,分而治之。这个方法的思想是,先把数列切割成左右两个部分,接下来,递归的把数列不断切割为两份,直到最小单位为一个元素。而这时,分别去求他们的子列和,并且在求算左半边和右半边的子列和之后,把跨越二分边界的子列和也求解出来。比较左半边的最大子列和,以及右半边的最大子列和,以及跨越边界的最大子列和。取出最大的那个数,即为整个数列的最大子列和。

这是一种很常用的算法思想,可以先看代码来理解一下。

    /**
     * 分治法,保持API一致
     * @param A 求解数列
     * @param N 元素总数
     * @return
     */
    public static int MaxSubseqSum3(int[] A, int N) {
        return DivideAndConquer(A, 0, N-1);
    }

    /**
     * 分治法主体
     * @param List 求解数列
     * @param left 左半边的下标
     * @param right 右半边的下标
     * @return 所求数列的最大子列和
     */ 
    public static int DivideAndConquer(int[] List, int left, int right) {
        int MaxLeftSum, MaxRightSum;
        int MaxLeftBorderSum, MaxRightBorderSum;
        int LeftBorderSum, RightBorderSum;
        int center, i;

        if (left == right) {
            if (List[left] > 0) {
                return List[left];
            } else {
                return 0;
            }
        }

        center = (left + right) / 2;
        
        //分解数列 不断递归调用
        MaxLeftSum = DivideAndConquer(List, left, center);
        MaxRightSum = DivideAndConquer(List, center + 1, right);
        
        //分别结算左右两边的跨越边界的和
        MaxLeftBorderSum = 0; LeftBorderSum = 0;
        for (i = center; i >= left; i--) {
            LeftBorderSum += List[i];
            if (LeftBorderSum > MaxLeftBorderSum) {
                MaxLeftBorderSum = LeftBorderSum;
            }
        }

        MaxRightBorderSum = 0; RightBorderSum = 0;
        for (i = center + 1; i <= right; i++) {
            RightBorderSum += List[i];
            if (RightBorderSum > MaxLeftBorderSum) {
                MaxRightBorderSum = RightBorderSum;
            }
        }
        return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
    }
    
     /**
     * 取三个数中的最大值
     * @return int
     */
    private static int Max3(int A, int B, int C) {
        return A > B ? A > C ? A : C : B > C ? B : C;
    }

而分治法的时间复杂度,是

T(1) = O(1)
T (N) = 2T(N/2) + cN
= 2 [2T( N/22 ) + cN/2] + cN
= 2kO(1) + ckN 
= O(NlogN )

现在我们可以看到,这个问题我们已经完成我们的降次目标了。那么还有更好的算法么?

在线处理

这个问题有个最简单的算法,叫在线处理法,遍历数列的时候,顺便累加,每次累加的和若是小于0,那么我们可以认为最大子列和为负数时,一定不会让后面的部分增大了,所以就可以把它丢弃,重新置当前的sum = 0

代码如下:

    public static int MaxSubseqSum4(int[] A, int N) {
        int ThisSum, MaxSum;
        int i;
        ThisSum = MaxSum = 0;
        for (i = 0; i < N; i++) {
            ThisSum += A[i];
            if (ThisSum > MaxSum) {
                MaxSum = ThisSum;
            } else if (ThisSum < 0) {
                ThisSum = 0;
            }
        }
        return MaxSum;
    }

在线处理的时间复杂度,因为是只遍历一遍,所以为T(N) = O(N)。 那么说了这么多,我们需要让事实来说话,我们现在准备一个30个元素的队列,让每个算法跑100000次来观察所需时间。

    public static void main(String[] args) {
        int size = 31;
        int[] testArr = {3, -1, 5, 10, -8, 2, 1, 4, 0, 7, -5, -6, 3, -8, -10,
                10, -20, -8, 0, 3, 0, -9, -10, 5, 3, 0, -8, 10, -4, 10, -7};
        int runCount = 100000;
        testFunction1(testArr, size, runCount);
        testFunction2(testArr, size, runCount);
        testFunction3(testArr, size, runCount);
        testFunction4(testArr, size, runCount);
    }

最后的log输出是这样的:

Max Subsequence Sum 1 is 23
function1 run time is  738ms
Max Subsequence Sum 2 is 23
function2 run time is  44ms
Max Subsequence Sum 3 is 17
function3 run time is  110ms
Max Subsequence Sum 4 is 17
function4 run time is  54ms

上面的function的标号,对应上面的4种方法,可以看到,如果我们真的用了第一种笨办法,那么他和高效算法之间的效率差距,实在是太大了。

算法的学习还要继续,多看书,多做题。那么我们下次再分享了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

算法导论第四章分治策略实例解析(一)

一、第三章简单回顾   中间略过了第三章, 第三章主要是介绍如何从数学层面上科学地定义算法复杂度,以致于能够以一套公有的标准来分析算法。其中,我认为只要记住三...

244100
来自专栏逸鹏说道

码农眼中的数学之~数学基础

1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

13430
来自专栏落影的专栏

程序员进阶之算法练习(三十)附基础教程

BAT常见的算法面试题解析:程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享,算法基础教程-。

25130
来自专栏TechBox

数据结构与算法系列之时间复杂度前言时间复杂度算法的空间复杂度

13530
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

40460
来自专栏自然语言处理

程序员眼中的统计学5

定义:若具有性质A的事件有m个,具有性质B的事件有n个,则具有性质A或性质B的事件有m+n个。

9130
来自专栏aCloudDeveloper

LeetCode:152_Maximum Product Subarray | 最大乘积连续子数组 | Medium

题目:Maximum Product Subarray Find the contiguous subarray within an array (contai...

21190
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

45550
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(01-05打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

6510
来自专栏程序员宝库

LCS 算法:Javascript 最长公共子序列

作者:司徒正美 链接:https://segmentfault.com/a/1190000012864957 最长公共子序列(Longest Common Su...

639100

扫码关注云+社区

领取腾讯云代金券