贪心算法专题(三)：负重前行，不如从头再来——「最大子序和」

哈喽各位，我是前端小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来记录当前累加的和。 从左向右遍历数组：

1. 累加：count += nums[i]。

2. 贪心决策：

   • 如果count变成了负数（比如-2），它对于后面的元素来说，就是一个“累赘”。

   • 因为：负数 + 下一个数 < 下一个数。

   • 后面的数会想：“与其加上你这个负数变小，我还不如自己另起炉灶！”

   • 策略：一旦count < 0，立刻把count重置为0（相当于放弃之前的序列，从下一个元素开始重新累加）。

注意：我们需要一个全局变量result来记录我们在过程中遇到的最大值。因为可能整个数组都是负数，或者最大和出现在中间某一段，而不是结尾。

算法流程

1. 初始化：

   • result = INT_MIN（或者nums[0]）：记录历史最大值。

   • count = 0：记录当前连续子序列的和。

2. 遍历数组：

   • count += nums[i]。

   • 更新最大值：if (count > result) result = count。这一步要在重置之前做，确保我们记录下了这一瞬间的高光时刻。

   • 贪心重置：if (count < 0) count = 0。如果当前和跌破 0，归零，重新开始。

3. 返回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，当天买当天卖都行），你怎么操作才能赚得最多？ 贪心策略简直简单到令人发指：只要今天比昨天贵，我就赚这个差价！

下期见！