算法笔记:最大子列和问题——分治法与动态规划

本文发布于 1.9 年前,最近编辑于 82 天前,请注意识别信息的时效性。

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

问题描述

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

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

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

的最大值。

本文将讲解解决这一问题的多种算法,试图优化算法的性能。代码将以 C/C++ 为例。如果你想看最快的算法,请直接跳到算法 4。

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

算法 1:简单暴力求解

既然要求最大子列和,那就把所有存在的子列和全部求出来,然后取最大的一个就行了。最简单的暴力求解,遍历所有的 i(子列起点)和 j(子列终点),没什么技巧性可言,且复杂度过大。

int max_subarray_1(int A[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tempSum = 0;  // 由当前i和j确定的子列的和
            for (int k = i; k <= j; k++) {
                tempSum += A[k];  // 从i加到j
            }
            if (tempSum > maxSum) {
                maxSum = tempSum;  // 更新最大值
            }
        }
    }
    return maxSum;
}

算法 2:暴力求解

算法 1 明显浪费时间。

在算法 1 中,计算的第一个子列为 $ \left \{ A_1 \right \} $,第二个子列为 $ \left \{ A_1, A_2 \right \} $,第三个子列为 $ \left \{ A_1, A_2, A_3 \right \} $……当 i 固定而 j 递增的时候,每次都是从头开始往后求和的。

对于同一个 i(子列起点),其实没有必要每次都从头开始求和,而是可以利用上一个计算出来的和,即使用一种“累加”的思想。这种方法依据的是以下公式:

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

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 \} $ 的最大子列和,必定是①②③中的最大值。

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

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

实现代码

int max_subarray_3(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:在线处理算法

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

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 ) $。这是最快的算法,因为无论如何都至少需要扫描一遍数列中的所有元素。

References

  1. 应用实例:最大子列和问题
  2. Maximum Subarray - LeetCode

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

添加新评论

已有 4 条评论

又做到这题,还可以动态规划

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

Jed Jed 回复 @boke112导航
0 0

谢谢

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