LeetCode53. 最大子数组和

53. 最大子数组和

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

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

解题思路

思路一： 动态规划

1. 定义状态（定义子问题）
dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。

2. 状态转移方程
根据状态的定义， nums[i]一定会被选取， 假设数组nums值全部都大于0， 则一定有 dp[i] = dp[i - 1] + nums[i]；
那么根据实际情况，现在就需要考虑dp[i - 1]的情况：

• dp[i - 1] > 0, 则 dp[i] = dp[i - 1] + nums[i]， 即可得到和更大的连续子数组；
• dp[i - 1] <= 0, 则 dp[i] = nums[i]， 因为dp[i - 1] + nums[i] < nums[i]；

以上两种情况的最大值就是dp[i]的值， 状态转移方程如下：
d p [ i ] = { d p [ i − 1 ] + n u m s [ i ] , i f d p [ i − 1 ] > 0 n u m s [ i ] , i f d p [ i − 1 ] < = 0 dp[i] =

dp[i]={dp[i−1]+nums[i],nums[i],​ifdp[i−1]>0ifdp[i−1]<=0​

即 $dp[i]=max(dp[i-1]+nums[i],nums[i])$

3. 初始条件
dp[0] = nums[0]；

4. 返回值
返回 dp 数组最大值，即可得到和更大的连续子数组

实现代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let len = nums.length,
        dp = Array(len).fill(0), 
        res = nums[0];
    dp[0] = nums[0];
    for (let i = 1; i < len; i++) {
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i];
        } else {
            dp[i] = nums[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

• 时间复杂度：O(n)，其中 n 为 nums 数组的长度
• 空间复杂度：O(n)

优化空间复杂度
考虑到 dp[i] 只和 dp[i - 1] 相关，于是我们可以只用一个变量 pre 来维护对于当前 dp[i] 的 dp[i - 1] 的值是多少，从而让空间复杂度降低到 O(1)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre = 0,
        res = nums[0];
    for (let num of nums) {
        pre = Math.max(pre + num, num);
        res = Math.max(res, pre);
    }
    return res;
};  
1
2
3
4
5
6
7
8
9
10
11
12
13

思路二： 分治法

取数组中心点为中心， 最大子序要么全在中心左边， 要么在右边，要么跨中心。 即分成三部分子区间：

• 子区间[left, mid];
• 子区间[mid + 1, right];
• 子区间[mid, mid + 1]; 由于 nums[mid] 与 nums[mid + 1] 一定会被选取，可以从中间向两边扩散，扩散到底 选出最大值

最后结果取三者最大的值。

实现代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let len = nums.length; 
    return maxSubArraySum(nums, 0, len - 1);
}

// 包含子区间[mid, mid + 1]， 即nums[mid]、nums[mid + 1]一定会被选取
var maxCrossingSum = function (nums, left, mid, right) {
    // 一定会包含 nums[mid] 这个元素
    let sum = 0;
    let leftSum = -10001;
    // 左半边包含 nums[mid] 元素，最多可以到什么地方
    // 走到最边界，看看最值是什么
    // 计算以 mid 结尾的最大的子数组的和
    for (let i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }
    sum = 0;
    let rightSum = -10001;
    // 右半边不包含 nums[mid] 元素，最多可以到什么地方
    // 计算以 mid+1 开始的最大的子数组的和
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }
    return leftSum + rightSum;
}

var maxSubArraySum = function (nums, left, right) {
    if (left == right) {
        return nums[left];
    }
    let mid = (left + right) >> 1;
    return max3(maxSubArraySum(nums, left, mid),
            maxSubArraySum(nums, mid + 1, right),
            maxCrossingSum(nums, left, mid, right));
}

var max3 = function (num1, num2, num3) {
    return Math.max(num1, Math.max(num2, num3));
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

• 时间复杂度：$O(nlogn)$，这里递归的深度是对数级别的，每一层需要遍历一遍数组（或者数组的一半、四分之一）；
• 空间复杂度：$O(logn)$，需要使用的空间取决于递归栈的深度

参考资料

经典动态规划问题（理解「无后效性」） - 最大子数组和 - 力扣（LeetCode）