剑指 Offer 42 连续子数组的最大和
概述
https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
https://leetcode.com/problems/maximum-subarray/
题目要求时间复杂度 O(n)。
动态规划法
状态定义：dp[i] 表示从第 i 个字符开始的子数组的最大和。
时间复杂度 O(n^2)，成功超时：
class Solution {
public:;
int maxSubArray(vector<int>& nums) {
vector<int> dp = nums;
int ans = dp[nums.size() - 1];
for (int i = nums.size() - 2; i >= 0; i --) {
int sum = nums[i];
for (int j = i + 1; j < nums.size(); j ++) {
dp[i] = max(dp[i], sum + dp[j]);
sum += nums[j];
}
ans = max(ans, dp[i]);
}
return ans;
}
};
实际上我们完全没必要遍历之后的选择呀，因为之后的选择，必然也是以 nums[i+1] 开头的，所以：
也就是说，这里的选择只有两个：
- 不要后一个元素，
- 要后一个元素。
时间复杂度降低到 O(n)：
class Solution {
public:;
int maxSubArray(vector<int>& nums) {
vector<int> dp = nums;
int ans = dp[nums.size() - 1];
for (int i = nums.size() - 2; i >= 0; i --) {
dp[i] = max(dp[i], dp[i] + dp[i+1]);
ans = max(ans, dp[i]);
}
return ans;
}
};
前缀和 + 左右指针
首先构造前缀和数组，之后左右指针逼近。
貌似还得动态规划，就不写了。
分治（求解任意区间的最大子段和）
维护 4 个变量：
- 以当前区间左端点为起点的最大子段和 lSum，
- 以当前区间右端点为终点的最大子段和 rSum，
- 当前区间的和 aSum，
- 当前区间的最大子段和 mSum。
class Solution {
public:
struct Sums {
int lSum, rSum, aSum, mSum;
};
int maxSubArray(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1).mSum;
}
Sums helper(vector<int>& nums, int l, int r) {
if (l == r) {
return {nums[l], nums[l], nums[l], nums[l]};
}
int m = (l + r) / 2;
Sums lSums = helper(nums, l, m);
Sums rSums = helper(nums, m + 1, r);
int aSum = lSums.aSum + rSums.aSum;
int lSum = max(lSums.lSum, lSums.aSum + rSums.lSum);
int rSum = max(rSums.rSum, rSums.aSum + lSums.rSum);
int mSum = max(max(lSums.mSum, rSums.mSum), lSums.rSum + rSums.lSum);
return {lSum, rSum, aSum, mSum};
}
};
相当于遍历了二叉树中的每一个节点，因此时间复杂度 O(n)。
递归使用 O(logn) 的栈空间，因此空间复杂度 O(logn)。
Links: sword-offer-42