【LeetCode】53、 最大子数组和

53、 最大子数组和

题目：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例1：

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

示例2：

输入：nums = [1]
输出：1
1
2

示例3：

输入：nums = [5,4,-1,7,8]
输出：23
1
2

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解题思路：

这是一道典型的使用「动态规划」解决的问题，需要我们掌握动态规划问题设计状态的技巧（无后效性），并且需要知道如何推导状态转移方程，最后再去优化空间。

关键 1：理解题意

题目要我们找出和最大的连续子数组的值是多少，「连续」是关键字，连续很重要，不是子序列。

题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。

关键 2：如何定义子问题（如何定义状态）

设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。

我们 不知道和最大的连续子数组一定会选哪一个数，那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。

例如，示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ，我们可以求出以下子问题：

• 子问题 1：经过 −2 的连续子数组的最大和是多少；
• 子问题 2：经过 1 的连续子数组的最大和是多少；
• 子问题 3：经过 -3 的连续子数组的最大和是多少；
• 子问题 4：经过 4 的连续子数组的最大和是多少；
• 子问题 5：经过 -1 的连续子数组的最大和是多少；
• 子问题 6：经过 2 的连续子数组的最大和是多少；
• 子问题 7：经过 1 的连续子数组的最大和是多少；
• 子问题 8：经过 −5 的连续子数组的最大和是多少；
• 子问题 9：经过 4 的连续子数组的最大和是多少。

一共 9 个子问题，这些子问题之间的联系并没有那么好看出来，这是因为 子问题的描述还有不确定的地方（这件事情叫做「有后效性」，我们在本文的最后会讲解什么是「无后效性」）。

例如「子问题 3」：经过 -3 的连续子数组的最大和是多少。

「经过 -3 的连续子数组」我们任意举出几个：

• [-2,1,-3,4] ，-3 是这个连续子数组的第 3 个元素；
• [1,-3,4,-1] ，-3 是这个连续子数组的第 2 个元素；
• 。。。。。。。

我们不确定的是：-3 是连续子数组的第几个元素。那么我们就把 −3 定义成连续子数组的最后一个元素。在新的定义下，我们列出子问题如下：

• 子问题 1：以 -2 结尾的连续子数组的最大和是多少；
• 子问题 2：以 1 结尾的连续子数组的最大和是多少；
• 子问题 3：以 −3 结尾的连续子数组的最大和是多少；
• 子问题 4：以 4 结尾的连续子数组的最大和是多少；
• 子问题 5：以 -1 结尾的连续子数组的最大和是多少；
• 子问题 6：以 2 结尾的连续子数组的最大和是多少；
• 子问题 7：以 1 结尾的连续子数组的最大和是多少；
• 子问题 8：以 -5 结尾的连续子数组的最大和是多少；
• 子问题 9：以 4 结尾的连续子数组的最大和是多少。

我们加上了「结尾的」，这些子问题之间就有了联系。我们单独看子问题 1 和子问题 2：

• 子问题 1：以 -2 结尾的连续子数组的最大和是多少；

以 −2 结尾的连续子数组是 [-2]，因此最大和就是 -2。

以 1 结尾的连续子数组有 [-2,1] 和 [1] ，其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2 + 1 = -1 < 1，因此「子问题 2」 的答案是 1。

参考代码：

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24