：负重前行，不如从头再来——「最大子序和」)
哈喽各位，我是前端小L。
欢迎来到贪心算法专题第三篇！ 我们要解决的问题很简单：给你一个整数数组（有正有负），让你找出一个连续的子数组，使得其和最大。
这道题如果用暴力法（两层循环枚举所有子数组），复杂度是 O(N2)，会超时。 如果用贪心（或者说动态规划的降维版），复杂度直接降为 O(N)。
力扣 53. 最大子序和
https://leetcode.cn/problems/maximum-subarray/
题目分析：
输入：整数数组
nums。目标：找到一个具有最大和的连续子数组。
输出：该子数组的和。
例子：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
连续子数组
[4, -1, 2, 1]的和是6，是最大的。
核心思维：什么时候该“放弃”？
我们需要一个变量count来记录当前累加的和。 从左向右遍历数组：
累加：
count += nums[i]。贪心决策：
如果
count变成了负数（比如-2），它对于后面的元素来说，就是一个“累赘”。因为：
负数 + 下一个数 < 下一个数。后面的数会想：“与其加上你这个负数变小，我还不如自己另起炉灶！”
策略：一旦
count < 0，立刻把count重置为0（相当于放弃之前的序列，从下一个元素开始重新累加）。
注意：我们需要一个全局变量result来记录我们在过程中遇到的最大值。因为可能整个数组都是负数，或者最大和出现在中间某一段，而不是结尾。
算法流程
初始化：
result = INT_MIN（或者nums[0]）：记录历史最大值。count = 0：记录当前连续子序列的和。
遍历数组：
count += nums[i]。更新最大值：
if (count > result) result = count。这一步要在重置之前做，确保我们记录下了这一瞬间的高光时刻。贪心重置：
if (count < 0) count = 0。如果当前和跌破 0，归零，重新开始。
返回
result。
代码实现 (C++)
C++
#include <vector> #include <climits> // for INT_MIN using namespace std; class Solution { public: int maxSubArray(vector<int>& nums) { int result = INT_MIN; // 最终结果 int count = 0; // 当前累加和 for (int i = 0; i < nums.size(); i++) { count += nums[i]; // 1. 累加 // 2. 取最大值 (必须放在重置之前，防止全负数的情况漏掉最大值) if (count > result) { result = count; } // 3. 贪心策略：如果当前和已经是负数了，就扔掉它 if (count < 0) { count = 0; } } return result; } };深度辨析：贪心 vs 动态规划
这道题其实也是经典的DP题目。
DP 定义：
dp[i]表示以nums[i]结尾的最大连续子数组和。转移方程：
dp[i] = max(dp[i-1] + nums[i], nums[i])。如果
dp[i-1]是负的，那就不要它了，直接取nums[i]。如果
dp[i-1]是正的，那就加上它。
观察：你看，这不就是我们的贪心逻辑吗？
count其实就是dp[i-1]，当它小于 0 时，我们重置为 0（相当于只取nums[i]）。
贪心写法只是把 DP 数组的空间优化到了 O(1) 而已。
深度复杂度分析
时间复杂度：O(N)
只需要遍历一次数组。
空间复杂度：O(1)
只需要两个变量
count和result。
总结：学会“及时止损”
今天这道题的贪心哲学非常实用：不要因为沉没成本而犹豫。当你发现当前的积累（count）已经变成负资产时，无论之前付出了多少努力（遍历了多少元素），都要果断“归零”，轻装上阵，才能在未来（后面的序列）取得更大的成就（result）。
下一题预告： 如果我们在炒股，这就更刺激了。 假设你能预知未来几天的股价，并且可以无限次地买入卖出（T+0，当天买当天卖都行），你怎么操作才能赚得最多？ 贪心策略简直简单到令人发指：只要今天比昨天贵，我就赚这个差价！
下期见！
