算法笔记:“最大子列和”问题的算法进化历程(C/C++)

请注意,本文编写于 326 天前,最后修改于 142 天前,其中某些信息可能已经过时。

问题描述

最大子列和问题:给定已知长度的整数数列,找出其中一段连续的子数列,使得该子数列的和最大。

用数学语言描述为:给定长度为 $ n $ 的整数数列$ \left \{ A_1, A_2, A_3, ..., A_n \right \} $,求函数

$$ f(i,j)=max \left \{ 0,\sum_{k=i}^{j}A_k \right \} $$

的最大值。

 

本文将依次讲解解决这一问题的 4 个逐渐优化(指时间复杂度)的算法,且采用伪代码C/C++ 语言进行描述。

本文地址:https://www.jeddd.com/article/maximum-subarray-algorithm.html

算法 1:非常暴力的暴力求解

既然要求最大子列和,那就把所有的子列和全部求出来,然后取最大的一个就行了。这就是暴力求解

伪代码

procedure 最大子列和算法1 (输入: 有n个数的数列A):
    maxSum = 0    // 初始化最大和为0
    for i = 0 to n:    // 子列左端
        for j = i to n:    // 子列右端
            tempSum = 0    // 当前子列和初始化为0
            for k = i to j:
                tempSum += A[k]
            if tempSum > maxSum:    // 若当前子列和大于已储存的最大和
                maxSum = tempSum    // 则更新最大和
    return maxSum

 

C/C++ 代码

int max_subarray1(int A[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tempSum = 0;
            for (int k = i; k <= j; k++) {
                tempSum += A[k];
            }
            if (tempSum > maxSum) {
                maxSum = tempSum;
            }
        }
    }
    return maxSum;
}

通过以上代码可以看出,该算法存在 3 层嵌套的 for 循环,故时间复杂度为 $ O\left ( N^3 \right ) $,一旦输入数据量很大(比如 100 万),该算法几乎没什么实际作用了。

 

算法 2:没那么暴力的暴力求解

算法 1 明显浪费时间。

在算法 1 中,计算的第一个子列为 $ \left \{ A_1 \right \} $,第二个子列为 $ \left \{ A_1, A_2 \right \} $,第三个子列为 $ \left \{ A_1, A_2, A_3 \right \} $……当 i 固定而 j 递增的时候,每次都是从头往后求和的,从而造成了资源浪费。我们可以利用以下公式优化求和这一步骤:

$$ \sum_{k=i}^{j+1}A_k=\sum_{k=i}^{j}A_k+A_{j+1} $$

伪代码

procedure 最大子列和算法2 (输入: 有n个数的数列A):
    maxSum = 0    // 初始化最大和为0
    for i = 0 to n:    // 子列左端
        tempSum = 0    // 从A[i]到A[j]的子列和
        for j = i to n:    // 子列右端
            tempSum += A[j]
            if tempSum > maxSum:    // 若当前子列和大于已储存的最大和
                maxSum = tempSum    // 则更新最大和
    return maxSum
本文地址:https://www.jeddd.com/article/maximum-subarray-algorithm.html

C/C++ 代码

int max_subarray2(int A[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int tempSum = 0;    // 对于固定的i,依次求从A[i]到A[j]的子列和
        for (int j = i; j < n; j++) {
            tempSum += A[j];
            if (tempSum > maxSum) {
                maxSum = tempSum;
            }
        }
    }
    return maxSum;
}

该算法存在 2 层嵌套的 for 循环,因此时间复杂度降到了 $ O\left ( N^2 \right ) $。

 

算法 3:递归与分治

算法思想

先将最初的数组一分为二,求其①左边的最大子列和,再求其②右边的最大子列和,再找到③跨越中间边界的最大子列和,三者之中的最大值就是我们要求的整个数列的最大子列和。

整个数列 $ \left \{ A_1, ..., A_9 \right \} $ 的最大子列和,必定是①②③中的最大值。

在上图中,①和②可以通过递归的方式得到

要想得到③,首先从中间边界开始向左“扫描”,得出一个最大和;然后再从中间边界开始向右扫描,得出另一个最大和;最后把向左和向右扫描出来的最大和相加,即是③。

限于篇幅,此处不再给出伪代码,请直接阅读 C/C++ 代码。

 

C/C++ 代码

int max_subarray3(int A[], int n) {
    if (n == 1) { return A[0]; }    // 若子列长度为1,则结束递归

    /* 左边的最大子列和 */
    int leftMaxSum = max_subarray3(&A[0], n / 2);

    /* 右边的最大子列和 */
    int rightMaxSum = max_subarray3(&A[n / 2], n - n / 2);

    /* 跨越中间边界的最大子列和 */
    int leftScanMaxSum = 0, rightScanMaxSum = 0;
    int tempSum = 0;
    for (int i = n / 2 - 1; i >= 0; i--) {    // 向左扫描
        tempSum += A[i];
        if (tempSum > leftScanMaxSum) { leftScanMaxSum = tempSum; }
    }
    tempSum = 0;    // 清零,供向右扫描使用
    for (int i = n / 2; i <= n; i++) {    // 向右扫描
        tempSum += A[i];
        if (tempSum > rightScanMaxSum) { rightScanMaxSum = tempSum; }
    }
    int midMaxSum = leftScanMaxSum + rightScanMaxSum;

    /* 答案是三种情况中的最大值 */
    int result = leftMaxSum;
    if (rightMaxSum > result) { result = rightMaxSum; }
    if (midMaxSum > result) { result = midMaxSum; }
    return result;
}

 

时间复杂度分析

递归算法的时间复杂度的分析稍稍困难一点。看到数学就头疼的同学可以跳过这段,直接看结论即可。

首先我们假设输入 $ N $ 个数据时需要进行 $ T\left ( N \right ) $ 步操作。(认为操作次数与时间成正比)

过程①和②是递归调用自身算法,但只处理一半数据,因此共需要进行 $ 2\cdot T\left ( \frac{N}{2} \right ) $ 次操作。

过程③中从边界向左、向右分别扫描了一次,因此过程③的时间复杂度应该为 $ O\left ( N \right ) $,所进行的操作次数为 $ N $ 的常数倍,设为 $ c\cdot N $。

由此得到关于 $ T\left ( N \right ) $ 的递推关系

$$ T\left ( N \right )=2\cdot T\left ( \frac{N}{2} \right )+c\cdot N $$

$$ T\left ( 1 \right )=O\left ( 1 \right ) $$

令 $ N=2^k $,如此递推下去:

综上所述,算法 3 的时间复杂度为 $ O\left ( N\log N \right ) $

 

算法 4:在线处理算法

所谓“在线处理”,意思就是每输入一个数据就进行即时处理。换句话说,在算法进行的任何时候中止输入,得到的结果都是在当前时刻正确的结果。

伪代码

procedure 最大子列和算法4 (输入: 有n个数的数列A):
    tempSum = 0
    maxSum = 0
    for i = 0 to N:
        tempSum += A[i]    // 依次向右累加
        if tempSum > maxSum:    // 若发现更大的子列和
            maxSum = tempSum    // 则更新当前结果
        else if tempSum < 0:    // 一旦当前子列和为负数
            tempSum = 0    // 则不可能使后续子列和变大。抛弃掉,归零
    return maxSum
本文地址:https://www.jeddd.com/article/maximum-subarray-algorithm.html

C/C++ 代码

int max_subarray4(int A[], int n) {
    int tempSum = 0, maxSum = 0;
    for (int i = 0; i < n; i++) {
        tempSum += A[i];
        if (tempSum > maxSum) {
            maxSum = tempSum;
        }
        else if (tempSum < 0) {
            tempSum = 0;
        }
    }
    return maxSum;
}

该算法的时间复杂度为 $ O\left ( N \right ) $,而且这是所有可能算法中最快的了。因为无论如何,我们都至少需要扫描一遍数列中的所有元素,仅仅扫描数列就需要时间复杂度 $ O\left ( N \right ) $ ,因此不可能有更快的算法了。

 

写在后面

首次在本站使用 LaTeX 编辑数学公式,如有纰漏敬请指正!

本文出自 Jed伪极客(www.jeddd.com),转载请注明出处。

参考资料:陈越《数据结构》

本文地址:https://www.jeddd.com/article/maximum-subarray-algorithm.html


Comments

添加新评论

已有 3 条评论

博主,你好,boke112导航特来拜会,已将贵站收录到博客导航的建站技术类,谢谢支持!

Jed Jed 回复 @boke112导航

谢谢

我就是看到公式就头疼的同学