nineloong's blog

题目描述

LeetCode 53 — 最大子数组和 (Medium)

给你一个整数数组 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

约束：

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

求解思路：分治

这道题要找的是连续子数组的最大和。一个自然的想法是枚举所有子数组——枚举左右端点，逐个求和比较，但这样是 $O(n^2)$ 的，面对 $10^5$ 的数据规模会超时。

换个角度，如果把数组从中间砍一刀，分成左右两半，那么最大子数组和只有三种可能：完全在左半边、完全在右半边、或者跨越中点。前两种递归求解即可，关键是第三种——跨越中点的子数组一定包含 nums[mid] 和 nums[mid+1]，那么从这两个位置分别向左右两边扩展，每步取更大的累加和，再把两侧的结果加起来就行。递归到底就是单元素，直接返回自身。这样每层做 $O(n)$ 的扫描，树高 $O(\log n)$ ，总时间 $O(n \log n)$ 。

解法一：分治

#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return maxSub(nums, 0, n - 1);
    }
private:
    int maxSub(vector<int>& nums, int left, int right) {
        if (left == right) return nums[left];
        int mid = left + (right - left) / 2;
        // 左半边最大和
        int a = maxSub(nums, left, mid);
        // 右半边最大和
        int b = maxSub(nums, mid + 1, right);
        // 跨越中点的最大和：包含 nums[mid] 和 nums[mid+1]
        int c = nums[mid] + nums[mid + 1];
        int cl = 0, cr = 0, temp = 0;
        // 向右扩展
        for (int i = mid + 2; i <= right; i++) {
            temp += nums[i];
            cr = max(cr, temp);
        }
        temp = 0;
        // 向左扩展
        for (int i = mid - 1; i >= left; i--) {
            temp += nums[i];
            cl = max(cl, temp);
        }
        c += cl + cr;
        return max(max(a, b), c);
    }
};

复杂度： 时间 $O(n \log n)$ ，空间 $O(\log n)$ （递归栈）。

求解思路：动态规划

分治能做，但这题有更简洁的解法。换个角度想：如果已经知道了以第 i-1 个元素结尾的最大子数组和，那么以第 i 个元素结尾的最大子数组和该怎么算？只有两种选择——要么把 nums[i] 接在前面那个子数组后面（dp[i-1] + nums[i]），要么从 nums[i] 重新开始（nums[i] 本身）。取两者的较大值就是答案。如果前面的累加和是负数，接上去只会让结果更小，不如重新开始。

这就是动态规划的状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])，其中 dp[i] 表示以第 i 个元素结尾的最大子数组和。答案就是所有 dp[i] 中的最大值。由于每个状态只依赖前一个，空间可以压缩到 $O(1)$ 。

解法二：动态规划

#include <vector>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < n; i++) {
            // 要么接在前面，要么重新开始
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

复杂度： 时间 $O(n)$ ，空间 $O(n)$ 。

空间可以进一步压缩到 $O(1)$ ，因为 dp[i] 只依赖 dp[i-1]，用一个变量滚动更新即可：

int maxSubArray(vector<int>& nums) {
    int cur = nums[0], ans = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        ans = max(ans, cur);
    }
    return ans;
}