LEETCODE ALGORITHM:53. Maximum Subarray

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: \[-2,1,-3,4,-1,2,1,-5,4\],
Output: 6
Explanation: \[4,-1,2,1\] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题解

dp

\[ 转移方程：f(i)=max\{f(i-1)+a_i,a_i\} \]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=nums[0],dp=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            dp=max(dp+nums[i],nums[i]);
            ans=max(dp,ans);
        }
        return ans;
    }
};

分治

对于一个区间 [l, r][l,r]，我们可以维护四个量：

  • lSum 表示 [l, r][l,r] 内以 ll 为左端点的最大子段和
  • rSum 表示 [l, r][l,r] 内以 rr 为右端点的最大子段和
  • mSum 表示 [l, r][l,r] 内的最大子段和
  • iSum 表示 [l, r][l,r] 的区间和

以下简称 [l, m][l,m] 为 [l, r][l,r] 的「左子区间」，\[m + 1, r\]\[m+1,r\] 为 \[l, r\]\[l,r\] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 [l, r][l,r] 的信息）？对于长度为 11 的区间 [i, i][i,i]，四个量的值都和 a_i*a**i* 相等。对于长度大于 11 的区间：

  • 首先最好维护的是 iSum，区间 [l, r][l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
  • 对于 [l, r][l,r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
  • 对于 [l, r][l,r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
  • 当计算好上面的三个量之后，就很好计算 [l, r][l,r] 的 mSum 了。我们可以考虑 [l, r][l,r] 的 mSum 对应的区间是否跨越 mm——它可能不跨越 mm，也就是说 [l, r][l,r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 mm，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
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
class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) return (Status) {a[l], a[l], a[l], a[l]};
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

分治参考

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/