LeetCode 一题多解 | 53. 最大子数组和：五种解法完全手册

点击上方“ 五分钟学算法 ”，选择“星标”公众号

作者：nettee
公众号：面向大象编程

一、原题描述

LeetCode 53. Maximum Subarray 最大子序和

二、全部解法

本文将介绍「最大子数组和」问题的以下五种解法：

其中，动态规划和贪心法其实是殊途同归，得到的是同样一份代码。分治法虽然时间复杂度不占优，却是最考验解题思路的一种方法。

本文对不同的解法都进行了时间复杂度的分析。关于时间复杂度的分析技巧可以参考文章： 时间复杂度分析快速入门：题型分类法 。

1. 暴力法：时间

暴力法是最容易想到的解法。我们可以直接根据题意，穷举各种可能的「子数组和」。

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = Integer.MIN_VALUE;
    // 穷举各种可能的子数组 nums[i..j]
    for (int i = 0; i         for (int j = i; j             // 计算子数组 nums[i..j] 的和
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += nums[k];                    
            }
            res = Math.max(res, sum);
        }
    }
    return res;
}

这个算法使用了三重循环，其中两层循环用于穷举所有可能的子数组，一层循环用于计算某个子数组的和。因此，算法的时间复杂度是 。

2. 暴力法的改进：时间

暴力法中使用的三重循环让时间复杂度变得非常大。我们可以通过一点简单的改进就能去掉一重循环，减少时间复杂度。

在上面的代码中，我们在第一层循环确定一个变量 i ，然后在第二层循环依次计算 nums[i..i] 、 nums[i..i+1] 一直到 nums[i..n-1] 的和。我们可以直接在一个 sum 变量上依次累加，而不需要使用第三层循环进行累加。

修改后的代码如下：

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = Integer.MIN_VALUE;
    for (int i = 0; i         int sum = 0;
        for (int j = i; j             sum += nums[j];
            res = Math.max(res, sum);
        }
    }
    return res;
}

这个算法只用了两重循环。我们在暴力法基础上进行简单的改进，就使得时间复杂度从 减少到了 。

3. 分治法：时间

分治法不是这道题时间复杂度最优的解法，但可能是这道题 最有挑战性的解法 。分治法的算法设计、时间复杂度分析都并不容易。这个解法建议详细阅读，赶时间的同学可以先跳到下一个解法。

既然是分治法，我们首先要考虑的就是如何「分」。要计算数组 nums 的最大子数组和，我们从数组中间将数组一分为二，则子数组可能位于：

• 左半部分数组
• 右半部分数组
• 中间（穿过中间线）

其中，位于左半部分数组和位于右半部分数组的子数组，可以通过递归调用继续求解，这便是分治法的「治」。

对于穿过中间线的子数组，我们可以分别计算「中间线左侧的最大子数组和」以及「中间线右侧的最大子数组和」，把它们相加就得到「穿过中间线的最大子数组和」。

将以上思路写成代码，我们可以得到以下的题解代码：

public int maxSubArray(int[] nums) {
    return maxSubArray(nums, 0, nums.length - 1




    
);
}

// 计算 nums[lo..hi] 的最大子数组和
// lo 表示 low，hi 表示 high
private int maxSubArray(int[] nums, int lo, int hi) {
    if (hi         return Integer.MIN_VALUE;
    } else if (hi == lo) {
        return nums[lo];
    }
    
    int mid = lo + (hi - lo) / 2;
    // 计算左半部分数组的最大子数组和
    int max_left = maxSubArray(nums, lo, mid);
    // 计算右半部分数组的最大子数组和
    int max_right = maxSubArray(nums, mid+1, hi);
    // 计算穿过中间线的子数组的最大和
    int max_mid = maxMidSubArray(nums, lo, mid, hi);
    return Math.max(max_left, Math.max(max_mid, max_right));
}

private int maxMidSubArray(int[] nums, int lo, int mid, int hi) {
    // 计算中间线左侧（且紧挨着中间线）的最大子数组和
    int max_mid_left = 0;
    if (mid >= lo) {
        max_mid_left = nums[mid];
        int sum = 0;
        for (int i = mid; i >= lo; i--) {
            sum += nums[i];
            max_mid_left = Math.max(max_mid_left, sum);
        }
    }
    
    // 计算中间线右侧（且紧挨着中间线）的最大子数组和
    int max_mid_right = 0;
    if (mid + 1 <= hi) {
        max_mid_right = nums[mid+1];
        int sum = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += nums[i];
            max_mid_right = Math.max(max_mid_right, sum);
        }
    }
    
    return max_mid_left + max_mid_right;
}

分治法的代码是写出来了，那么怎么证明这个算法的时间复杂度就是 呢？

其实，我们可以把这个算法跟经典的「归并排序」做个对照，两者是非常相似的：

• 在「分」的过程，都是将数组平均分成了两半；
• 在「治」的过程，都是对数组的左右两半做递归调用；
• 都需要做一个额外的操作，这个算法中是计算穿过中间线的最大子数组，归并排序中是将左右两侧排好序的数组进行 merge，额外操作的时间复杂度都是 。

既然这个算法在各方面都可以和归并排序对应上，那么这个算法的时间复杂度一定也和归并排序一样，是 。

4. 动态规划：时间

动态规划的基本思路

这道题的动态规划解法在文章「 子数组类问题的动态规划技巧 」中讲解过。本文重新梳理了之前的讲解，还会讨论空间优化的方法。

我们还是使用动态规划的「解题四步骤」求解（关于四步骤的基础讲解，可以参考 这篇文章 ）：

• 定义子问题
• 写出子问题的递推关系
• 确定 DP 数组的计算顺序
• 空间优化

由于这道题计算的是「最大子数组和」，我们使用一个「子数组」类题目的常见技巧，在定义子问题的时候加上 位于数组尾部 的限制条件。

我们定义子问题 表示「 nums[0..k) 中， 以最后一个元素结尾的 最大子数组和」，那么原问题可以表示为 。

在子问题中限制结果位于数组尾部，是为了将当前的最优结果跟后面新加入的元素能够拼接起来，如下图所示：

接着，我们写出子问题的递推关系：

这个递推公式的含义是，计算 nums[0..k) 的最大子数组和时，要么是把新元素 nums[k-1] 加入前一个子问题的结果（即 的含义），要么是只使用元素 nums[k-1] ，选择其中结果较大的一个方案。

这个递推公式可以化简为：

可以看到，子问题的依赖关系非常简单，在计算 DP 数组时，从左到右计算即可。这样我们可以写出如下的题解代码：

public int maxSubArray(int[] nums) {
    // 子问题：
    // f(k) = nums[0..k) 中以 nums[k-1] 结尾的最大子数组和
    // 原问题 = max{ f(k) }, 0 <= k <= N

    // f(0) = 0
    // f(k) = max{ f(k-1), 0 } + nums[k-1]

    int N = nums.length;
    int[] dp = new int[N+1];
    dp[0] = 0;

    int res = Integer.MIN_VALUE;
    for (int k = 1; k <= N; k++) {
        dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
        res = Math.max(res, dp[k]);
    }
    return res;
}

时间复杂度 ，空间复杂度 。

动态规划的空间优化

上面的动态规划代码已经非常高效了。不过经过一些空间优化手段，可以让代码更加简洁，也可以让空间复杂度降低到 。

首先，由于每个子问题只需要通过上一个子问题计算出来，我们不需要保存整个一维 DP 数组，用单个变量保存即可：

public int maxSubArray(int[] nums) {
    int dp = 0;
    int res = Integer.MIN_VALUE;
    for (int k = 1; k <= nums.length; k++) {
        dp = Math.max(dp, 0) + nums[k-1];
        res = Math.max(res, dp);
    }
    return res;
}

其中的 for 循环还可以做下标优化，变成 for-each 循环：

public int maxSubArray(int[] nums) {
    int dp = 0