LeetCode 53 - 最大子数组和

思路：动态规划

关键：当前元素 nums[i] 结尾的最大子数组和

1. 定义状态：cur 表示以当前元素结尾的最大子数组和，maxAns 表示全局最大和。
2. 决策：遍历数组，对于每个元素 nums[i]，我们做个选择：
   • 如果前一段的和 (cur) 是负数，那它就是个累赘，丢掉，让 nums[i] 自立门户。此时 cur = nums[i]。
   • 如果前一段的和是正数，那它有增益效果，应该把它加上。此时 cur = cur + nums[i]。
3. 状态转移：以上可合并为 cur = max(nums[i], cur + nums[i])。
4. 更新结果：每一步都用 cur 更新全局 maxAns。

C++ 代码实现

class Solution {
public:int maxSubArray(vector<int>& nums) {int cur=0,maxAns=nums[0];for(const auto &x:nums){cur=max(cur+x,x);maxAns=max(maxAns,cur);}return maxAns;}
};

复杂度

• 时间复杂度: O(n)，单次遍历。
• 空间复杂度: O(1)，常数空间。

进阶：分治法

分治法解决，复杂度 O(n log n) 不如动态规划的 O(n)

1. 分解 (Divide)：将数组从中间一分为二，分成左右两个子数组。
2. 解决 (Conquer)：递归地计算左子数组的最大子数组和 (left_max)，以及右子数组的最大子数组和 (right_max)。
3. 合并 (Combine)：最大子数组和可能出现在三个地方：
   • 完全位于左子数组中（即 left_max）。
   • 完全位于右子数组中（即 right_max）。
   • 跨越中点。需要单独计算：从中点开始向左找最大和，再从中点开始向右找最大和，两者相加。
4. 最终结果是这三者中的最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {}
};