interviewalgo
, , , , ,
Source
Edit
History

53. 最大子序和

Introduction

Question：53. 最大子序和

解法一

Analysis

假设最大子序和的连续子数组为 A[i:j]，那么 sum(A[i:k]) >= 0，i < k <= j

使用两个指针 first 和 last 标识当前连续子数组的范围，利用上面这个性质，我们可以快速移动指针。

具体的操作：

  • 当 sum(A[first:last+1]) <= 0 时，first = last = last + 1;
  • 当 sum(A[first:last+1]) > 0 时，maxSum = max(maxSum, sum(A[first:last+1])); last++;

直到 last >= len(A)

Implement

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
    int res = INT_MIN, tempSum = 0;
    int first, last;
    for(first = 0, last = 0; last < nums.size(); last++) {
        tempSum += nums[last];
        res = max(res, tempSum);
        if (tempSum < 0) { first = last + 1; tempSum = 0;}
    }
    return res;
}

更简洁的写法：

1
2
3
4
5
6
7
8
9
int maxSubArray(vector<int>& nums) {
    int res = nums[0], tempSum = 0;
    for(auto &n: nums) {
        tempSum += n;
        res = max(res, tempSum);
        tempSum = max(tempSum, 0);
    }
    return res;
}

解法二

Analysis

当意识到这道题可以用分治法做时，一般答案就快出来了，因为分治通常的模式都非常相近。

先把假设能求出子问题，然后去想要如何利用子问题的结果来求解原问题。这个思考过程和 DP 很像，但是 DP 通常子问题规模是 n-1 ，而分治则是 n/2。

已这道题为例子，输入为 A[first:last+1]

一个数组的最大子序之和只有三种可能：

  • 在数组的前半部分，即 A[first:mid]
  • 在数组的后半部分，即 A[mid+1:last+1]
  • 一半在数组的前半部分，一半在数组的后半部分

如果我们已经知道数组前半部分和后半部分的最大子序之和，我们只需要求解第三种情况，即可得到原问题的解

而第三种情况又是比较容易求解的，

即 max_{first <= k <= mid} (sum(A[k:mid])) + max_{mid+1 <= k <= last+1} (sum(A[mid+1:k]))

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxSubArray(vector<int>& nums) {
    return maxSubArray(nums, 0, nums.size()-1);
}
int maxSubArray(vector<int> nums, int first, int last) {
    if (first == last) return nums[first];
    int mid = (first+last)/2;
    // first:mid
    int leftSum = nums[mid];
    int temp = 0;
    for(int i = mid;i >= first;i--) {
        temp += nums[i];
        leftSum = max(leftSum, temp);
    }
    int rightSum = nums[mid+1];
    temp  = 0;
    for(int i = mid+1;i <= last; i++) {
        temp += nums[i];
        rightSum = max(rightSum, temp);
    }
    temp = max(maxSubArray(nums, first, mid), maxSubArray(nums, mid+1, last));
    return max(rightSum + leftSum, temp);
}

One More Thing