题目描述
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
样例
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6。
输入:nums = [1]
输出:1
输入:nums = [0]
输出:0
输入:nums = [-1]
输出:-1
输入:nums = [-100000]
输出:-100000
限制
1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5
进阶
- 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
算法1
(动态规划) O(n)
- 设 f(i) 表示以第 i 个数字为结尾的最大连续子序列的 总和 是多少。
- 初始化 f(0)=nums[0]。
- 转移方程 f(i)=max。可以理解为当前有两种决策,一种是将第 i 个数字和前边的数字拼接起来;另一种是第 i 个数字单独作为一个新的子序列的开始。
- 最终答案为 ans = \max (f(k)), 0 \leq k < n。
时间复杂度
- 状态数为 O(n),转移时间为 O(1),故总时间复杂度为 O(n)。
空间复杂度
- 需要额外 O(n) 的空间存储状态。
- 可以通过一个变量来替代数组将空间复杂度优化到常数。
C++ 代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size(), ans;
vector<int> f(n);
f[0] = nums[0];
ans = f[0];
for (int i = 1; i < n; i++) {
f[i] = max(f[i - 1] + nums[i], nums[i]);
ans = max(ans, f[i]);
}
return ans;
}
};
算法2
(分治) O(n \log n)
- 考虑区间
[l, r]
内的答案如何计算,令mid = (l + r) / 2
,则该区间的答案由三部分取最大值,分别是:
(1). 区间[l, mid]
内的答案(递归计算)。
(2). 区间[mid + 1, r]
内的答案(递归计算)。
(3). 跨越mid
和mid + 1
的连续子序列。 - 其中,第 (3) 部分只需要从
mid
开始向l
找连续的最大值,以及从mid+1
开始向r
找最大值即可,在线性时间内可以完成。 - 递归终止条件显然是
l == r
,此时直接返回nums[l]
。
时间复杂度
- 由递归主定理 T(n) = 2T(n/2) + O(n),解出总时间复杂度为 O(n \log n)。
- 或者每一层时间复杂度是 O(n),总共有 O(\log n) 层,故总时间复杂度是 O(n\log n)。
空间复杂度
- 需要额外 O(\log n) 的空用于递归的系统栈。
C++ 代码
class Solution {
public:
int calc(int l, int r, vector<int>& nums) {
if (l == r)
return nums[l];
int mid = (l + r) >> 1;
int lmax = nums[mid], lsum = 0, rmax = nums[mid + 1], rsum = 0;
for (int i = mid; i >= l; i--) {
lsum += nums[i];
lmax = max(lmax, lsum);
}
for (int i = mid + 1; i <= r; i++) {
rsum += nums[i];
rmax = max(rmax, rsum);
}
return max(max(calc(l, mid, nums), calc(mid + 1, r, nums)), lmax + rmax);
}
int maxSubArray(vector<int>& nums) {
int n = nums.size();
return calc(0, n - 1, nums);
}
};
算法3
(分治) O(n)
- 对于一个区间 [l, r],维护四个值,分别是:总和 sum;非空最大子段和 s;前缀非空最大子段和 ls;后缀非空最大子段和 rs。
- 分别递归左右子区间。
- 合并时,对于 sum 则是左右子区间的 sum 之和。
- 对于 s,则有三种情况取最大值:左区间的 s;右区间的 s;左区间的 rs 加上右区间的 ls。
- 对于 ls,则有两种情况取最大值:左区间的 ls;左区间的 sum 加上右区间的 ls。
- 对于 rs 同理。
- 合并后返回递归的结果。
时间复杂度
- 由递归主定理 T(n) = 2T(n/2) + O(1),解出总时间复杂度为 O(n)。
空间复杂度
- 需要额外 O(\log n) 的空用于递归的系统栈。
struct Node {
int sum, s, ls, rs;
Node(int sum_, int s_, int ls_, int rs_) {
sum = sum_; s = s_; ls = ls_; rs = rs_;
}
};
class Solution {
public:
Node solve(int l, int r, const vector<int> &nums) {
if (l == r)
return Node(nums[l], nums[l], nums[l], nums[l]);
int m = (l + r) >> 1;
Node left = solve(l, m, nums);
Node right = solve(m + 1, r, nums);
return Node(
left.sum + right.sum,
max(max(left.s, right.s), left.rs + right.ls),
max(left.ls, left.sum + right.ls),
max(right.rs, left.rs + right.sum)
);
}
int maxSubArray(vector<int>& nums) {
return solve(0, nums.size() - 1, nums).s;
}
};
补充,同样是递归思想,空间复杂度为哦o(1)
public int maxSubArray(int[] nums) { if (nums.length < 1) return 0; int cur = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++){ if (cur <= 0){ cur = nums[i]; } else { cur += nums[i]; } max = Math.max(max, cur); } return max; }
没错!赞一个
这个是递推思想,不过简化了空间复杂度,利用转移的性质优化掉了数组!
用分治写的话怎么记录连续的子段
递归返回的时候再额外传左右端点的坐标
可以附一段代码吗
算法3,再在结构体里额外定义一个pair表示左右端点。返回的时候,根据不同的决策情况,拼接不同的端点。枚举的情况比较多
贴一个
y总分治
时间O(n)
的代码:// 分治:y总 时间O(n), 空间 O(logn) class Solution { public: struct status { int sum, s, ls, rs; // 区间总和, 最大子段和, 最大前缀和, 最大后缀和 }; status build(vector<int>& nums, int l, int r) { if (l == r) return {nums[l], nums[l], nums[l], nums[l]}; int mid = l + r >> 1; auto L = build(nums, l, mid), R = build(nums, mid + 1, r); status LR; LR.sum = L.sum + R.sum; LR.s = max(max(L.s, R.s), L.rs + R.ls); LR.ls = max(L.ls, L.sum + R.ls); LR.rs = max(R.rs, R.sum + L.rs); return LR; } int maxSubArray(vector<int>& nums) { int n = nums.size(); auto res = build(nums, 0, n - 1); return res.s; } };
赞
/* 思路2:分治法/线段树 L区间、R区间平分M区间,分界点mid = (L+R) >> 1 M.mSum = max(L.mSum, R.mSum, L.rightSum + R.leftSum) //mSum代表区间最大子序和。L.rightSum + R.leftSum代表跨越分界点的连续子序列 M.leftSum = max(L.leftSum, L.totalSum + R.leftSum) // leftSum代表从L为起点向R的最大连续前缀和 M.rightSum = max(R.rightSum, R.totalSum + L.rightSum) // rightSum代表从R为起点向L的最大连续前缀和 M.totalSum = L.totalSum + R.totalSum //区间和 */ class Solution { public: tuple<int, int, int, int> calc(int l, int r, vector<int>& nums) { if (l == r) return make_tuple(nums[l], nums[l], nums[l], nums[l]); int mid = (l + r) >> 1; int L_mSum, L_leftSum, L_rightSum, L_totalSum; int R_mSum, R_leftSum, R_rightSum, R_totalSum; int mSum, leftSum, rightSum, totalSum; tie(L_mSum, L_leftSum, L_rightSum, L_totalSum) = calc(l, mid, nums); tie(R_mSum, R_leftSum, R_rightSum, R_totalSum) = calc(mid + 1, r, nums); mSum = max(max(L_mSum, R_mSum), L_rightSum + R_leftSum); leftSum = max(L_leftSum, L_totalSum + R_leftSum); rightSum = max(R_rightSum, R_totalSum + L_rightSum); totalSum = L_totalSum + R_totalSum; return make_tuple(mSum, leftSum, rightSum, totalSum); } int maxSubArray(vector<int>& nums) { int n = nums.size(); int a, b, c, d; tie(a, b, c, d) = calc(0, n - 1, nums); return a; } };
这里求左边的最大值的时候,为什么改成
for(int i = l; i<=mid; i++)
就出错了呢
左边应该是以右端点开始向左的“累加和”才对
这里
vector<int> f(n);
如果改成vector<int> f;
, 为什么会报错,vector 不是相当于长度可以动态变化的int数组么?vector<int> f;
是用默认的构造函数定义一个空的f
数组。vector<int> f(n);
是定义一个预先分配了n
个元素的数组,但元素的值未初始化。可以看一下 vector 的资料。好的,谢谢,我刚开始接触C++, 基础太差了。
请问下递归写法里面的
lmax + rmax是代表上面第三部分的情况吗,不太明白
是的