问题描述

给定一个整数序列，找到一个具有最大和的连续子序列（至少包含一个元素），返回其最大和。

示例：

输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6 。

本文将讲解这一问题的 5 种解法，试图优化算法的性能。其中算法 4 和算法 5 的时间复杂度最低。代码以 C++ 为例。

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

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

算法 1：暴力求解

两层循环遍历所有可能的起点 $i$ 和终点 $j$，取使子列和最大的组合。

int maxSubArray(vector<int>& nums) {
    int max_sum = INT_MIN;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i; j < nums.size(); j++) {
            int sum = 0;  // 由当前i和j确定的子列和
            for (int k = i; k <= j; k++) sum += nums[k];
            max_sum = max(sum, max_sum);
        }
    }
    return max_sum;
}

时间复杂度为 $O(n^3)$。

算法 2：暴力求解（通过累加优化）

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

对于一个固定的 $i$，当 $j$ 递增时，可以利用上一个 $j$ 计算出来的和，通过累加的方法求出当前的和。即：

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

int maxSubArray(vector<int>& nums) {
    int max_sum = INT_MIN;
    for (int i = 0; i < nums.size(); i++) {
        int sum = 0;  // 固定i，递增j，累加求和
        for (int j = i; j < nums.size(); j++) {
            sum += nums[j];
            max_sum = max(sum, max_sum);
        }
    }
    return max_sum;
}

时间复杂度为 $O(n^2)$。

算法 3：分治法

算法思想

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

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

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

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

实现代码

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];

    vector<int> nums_left(nums.begin(), nums.begin() + n / 2);
    vector<int> nums_right(nums.begin() + n / 2, nums.end());
    int max_sum_left = maxSubArray(nums_left);    // 左边的最大子列和
    int max_sum_right = maxSubArray(nums_right);  // 右边的最大子列和

    // 跨越中间边界的最大子列和
    int scan_sum_left = INT_MIN, scan_sum_right = INT_MIN;
    int sum = 0;
    for (int i = n / 2 - 1; i >= 0; i--) {  // 向左扫描
        sum += nums[i];
        scan_sum_left = max(sum, scan_sum_left);
    }
    sum = 0;
    for (int i = n / 2; i < n; i++) {  // 向右扫描
        sum += nums[i];
        scan_sum_right = max(sum, scan_sum_right);
    }
    int max_sum_mid = scan_sum_left + scan_sum_right;

    return max({max_sum_left, max_sum_right, max_sum_mid});
}

时间复杂度分析

首先我们假设输入 $n$ 个数据时需要进行 $T(n)$ 步操作。

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

过程③中从中间向左、向右分别扫描累加了一次，因此过程③进行的操作次数为 $n$ 的常数倍，设为 $c\cdot n$。

由此得到关于 $T(n)$ 的递推关系（认为操作次数与时间成正比）：

$$ T(n)=2\cdot T(\frac{n}{2})+c\cdot n $$

$$ T(1)=O(1) $$

令 $n=2^k$，如此递推下去：

$$ \begin{align*} T(n)&= 2\cdot T( \frac{n}{2} ) + c\cdot n \\ &= 2^2\cdot T( \frac{n}{2^2} ) + 2\cdot c\cdot n \\ &= \cdots \\ &= 2^k\cdot T(1) + k\cdot c\cdot n \\ &= n\cdot O(1) + \log n\cdot c\cdot n \\ &= O(n\log n) \end{align*} $$

综上，时间复杂度为 $O(n\log n)$。

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

算法 4：动态规划

动态规划算法依据一个事实：最大子列不可能存在累加和为负的前缀，否则将该前缀去除后的子列和更大。

令 $\text{dp}_i$ 表示以 $A_i$ 为结尾的最大子列和（必须包含 $A_i$），则 $\text{dp}_i$ 可以由 $\text{dp}_{i-1}$ 推得，分为两种情况讨论：

  1. $\text{dp}_{i-1} < 0$：以 $A_{i-1}$ 为结尾的最大子列和为负，则 $(\text{dp}_{i-1}+A_i)$ 还不如 $A_i$ 本身大，所以直接丢弃这个累加和为负的前缀；
  2. $\text{dp}_{i-1}\ge 0$：前缀的累加和为正，因此保留该前缀可使当前子列和更大。

状态转移方程：

$$ \text{dp}_i = \begin{cases} A_i, &\text{dp}_{i-1}<0, \\ \text{dp}_{i-1} + A_i, &\text{dp}_{i-1} \ge 0 \end{cases} $$

最后，$\text{dp}$ 数组的最大值即为所求。

int maxSubArray(vector<int>& nums) {
    int dp[nums.size()];
    dp[0] = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (dp[i - 1] < 0)
            dp[i] = nums[i];
        else
            dp[i] = dp[i - 1] + nums[i];
    }
    int max_dp = INT_MIN;
    for (int i = 0; i < nums.size(); i++) max_dp = max(dp[i], max_dp);
    return max_dp;
}

时间复杂度为 $O(n)$。这是最快的算法，因为任何算法都至少需要扫描一遍数列中的所有元素。

算法 5：在线处理

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

该算法是动态规划的优化版本，将最后遍历 $\text{dp}$ 数组的操作与遍历 nums 本身合为一次循环，同时免去了开辟 $\text{dp}$ 数组以节省空间。

int maxSubArray(vector<int>& nums) {
    int max_sum = INT_MIN;
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (sum < 0)
            sum = nums[i];  // 一旦子列和为负，则丢弃
        else
            sum += nums[i];
        max_sum = max(sum, max_sum);
    }
    return max_sum;
}

时间复杂度为 $O(n)$。

References

  1. 应用实例：最大子列和问题 - 数据结构_中国大学MOOC(慕课)
  2. Maximum Subarray - LeetCode
  3. 剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）

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