代码拉取完成,页面将自动刷新
// 力扣 53. 最大子数组和(中等)Hot100
// https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
//
// 思路:Kadane 动态规划,cur 表示以当前元素结尾的最大和
// 设 curSum = "以当前下标 i 结尾"的最大子数组和,那么:
// 要么 nums[i] 单独成段: curSum = nums[i]
// 要么接在前一个的后面: curSum = 前一个的 curSum + nums[i]
// 取两者较大值即可。为什么只看这两种?因为任何以 i 结尾的子数组
// 去掉 nums[i] 之后,要么是空的(单独成段),要么是以 i-1 结尾的某个子数组。
// 而要让"加上 nums[i] 之后"最大,那前面的那段自然也要取最大的,
// 所以"以 i-1 结尾的最大和"就够用了,这就是最优子结构。
// 全程只需要滚动两个变量,所以空间 O(1)。
//
// 版本一:Kadane,O(n) 时间 / O(1) 空间,标准答案。
// 版本二:分治,O(n log n),面试有时会追问"不用 DP 怎么做",或者"数据太大要并行"。
// 分治的好处是可并行、可处理流式拼接,缺点是常数大、代码长。
//
// 时间复杂度:
// 版本一:O(n),一趟扫描
// 版本二:O(n log n),T(n) = 2T(n/2) + O(n)
// 空间复杂度:
// 版本一:O(1),只有 curSum 和 maxSum 两个变量
// 版本二:O(log n),递归栈深度
//
// 易错点:全负数时答案不是 0,cur 要初始化为 nums[0] 或 -INF
// 1. 两个变量都必须初始化为 nums[0],不能初始化为 0。
// 如果写成 0,遇到 [-3,-1,-2] 会返回 0,正确答案是 -1。
// 2. curSum 的含义是"以当前元素结尾",不是"当前最优"。别把两者搞混:
// 当前最优可能存在 maxSum 里,而 curSum 允许是负数(因为后面可能翻盘)。
// 3. 更新顺序不能反:先更新 curSum,再用新的 curSum 更新 maxSum。
// 4. 版本二里"跨中点"的那部分必须至少包含 nums[mid] 和 nums[mid+1],
// 否则会退化成单侧,和左右递归的结果重复计算。
//
// 面试口述要点:
// 1. 先说暴力:枚举左右端点再求和,O(n³);用前缀和降到 O(n²);
// 2. 再给最优子结构:curSum(i) = max(nums[i], curSum(i-1) + nums[i]),
// "接上前面"或"从自己重新开始",二选一,一趟扫完 O(n);
// 3. 主动说出全负数的坑:初始化为 nums[0] 而不是 0,这是最常见的 WA;
// 4. 如果被追问"还有别的方法吗",给分治:最大值只有三种可能——
// 完全在左半、完全在右半、跨过中点,第三种用"以 mid 结尾的最大后缀 +
// 以 mid+1 开头的最大前缀"算出,总复杂度 O(n log n)。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:Kadane(动态规划 + 滚动变量),O(n) 时间 / O(1) 空间
// curSum : 以当前下标结尾的最大子数组和
// maxSum : 目前为止见过的最优答案
// ================================================================
int maxSubArray(vector<int>& nums) {
int n = (int)nums.size();
// 注意:初始化为 nums[0],不是 0
int curSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < n; i++) {
// 二选一:接上前面的,或者从 nums[i] 重新开始
curSum = max(nums[i], curSum + nums[i]);
// 先更新完 curSum,再用它更新 maxSum
maxSum = max(maxSum, curSum);
}
return maxSum;
}
// ================================================================
// 版本二:分治,O(n log n)
// 区间 [left, right] 上的最大子数组和只有三种可能:
// 1) 完全在左半边 [left, mid];
// 2) 完全在右半边 [mid+1, right];
// 3) 跨过中点:必须以 nums[mid] 结尾的一段 + 必须以 nums[mid+1] 开头的一段。
// 前两种递归,第三种在 O(right-left+1) 内扫出来。
// ================================================================
int maxSubArray_v2(vector<int>& nums) {
return solve(nums, 0, (int)nums.size() - 1);
}
private:
int solve(vector<int>& nums, int left, int right) {
if (left == right) { // 只有一个数,只能是它自己
return nums[left];
}
int mid = left + (right - left) / 2; // 这样写避免 left+right 溢出
// ---------- 情形 1 和 2:完全在某一侧 ----------
int bestLeft = solve(nums, left, mid);
int bestRight = solve(nums, mid + 1, right);
// ---------- 情形 3:跨过中点 ----------
// 左半边:必须以 nums[mid] 结尾,往左扩展取最大
int leftPart = nums[mid];
int sum = 0;
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftPart = max(leftPart, sum);
}
// 右半边:必须以 nums[mid+1] 开头,往右扩展取最大
int rightPart = nums[mid + 1];
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightPart = max(rightPart, sum);
}
int bestCross = leftPart + rightPart;
// ---------- 三种情况取最大 ----------
return max(max(bestLeft, bestRight), bestCross);
}
};
// 本地测试:输入 n,然后 n 个整数;输出最大子数组和
// 同时跑两个版本并比对结果,方便验证优化版和原版等价
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
int ans1 = Solution().maxSubArray(nums);
int ans2 = Solution().maxSubArray_v2(nums);
if (ans1 != ans2) {
cout << "MISMATCH: v1=" << ans1 << " v2=" << ans2 << '\n';
return 0;
}
cout << ans1 << '\n';
return 0;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。