009 · Maximum Subarray
My First Thoughts
初次看到这个题，很自然会把它想成：
用一个不定长的框，去框住
nums里的某个连续区间，让这个区间的和尽量大。
因为题目要求的是连续子数组，所以第一反应往“区间”上靠，其实是很正常的。
而且它会让人想到前面的 Best Time to Buy and Sell Stock。那题里我们也是一边往右走，一边维护“到当前位置为止的最好状态”。
于是这里很容易先想到：
- 右边界
right一定要有，因为我们总得知道当前看到哪里了 - 如果只记右边界，那每到一个新位置，都要重新计算前面很多区间和，显然太慢
- 所以是不是还需要一个
left，表示当前认为比较好的左边界？
顺着这个想法，脑子里很容易出现类似这样的思路：
left = 0
best = nums[0]
for right in range(len(nums)):
total = sum(nums[left:right + 1])
if total >= best:
best = total
next_total = sum(nums[left + 1:right + 1])
if next_total >= best:
left += 1
best = next_total这个方向的直觉并不离谱。它其实已经抓到了两个点：
- 这是一个连续区间问题
- 不能每次都把所有组合从头算一遍
Why That Is Not Enough
问题出在：这题虽然看起来像“区间”题，但它不是一个适合标准滑动窗口的题。
原因是数组里有负数。
一旦有负数，窗口的和就不具备那种“边扩边缩、单调调整”的性质。也就是说，左边界不是像普通窗口题那样，一点一点往右挪就能稳定逼近答案。
更具体地说，前面的这一类想法有两个问题。
第一，反复计算区间和会很慢。
像这样：
sum(nums[left:right + 1])如果每一轮都重新算一次，总复杂度最坏会接近 \(O(n^2)\)。
第二，左边界不是“慢慢前进一步”就够了。
有时候真正正确的决定不是：
- 把左边界往右挪一格
而是：
- 直接把前面整段全部丢掉
- 从当前位置重新开始
比如：
[-100, 4, -1, 2]当看到后面的 4 时，前面的 -100 已经不是“需要微调的左边界”，而是应该被彻底舍弃的拖累。
所以这题真正关键的不是：
当前最优区间的左边界到底在哪？
而是：
以当前位置结尾的最大连续子数组和，是多少？
这个视角一换，题目就顺了。
Final Idea
定义一个状态 current，表示：
以当前位置结尾的最大连续子数组和
当我们走到 nums[i] 时，只有两种选择：
- 让
nums[i]自己单独开始一个新的子数组 - 把
nums[i]接到前面的连续子数组后面
所以状态转移就是：
current = max(nums[i], current + nums[i])然后再用一个 best，记录遍历过程中出现过的最大值：
best = max(best, current)这里其实已经把“左边界怎么处理”隐含进去了。
如果：
nums[i] > current + nums[i]说明前面的累计和已经变成负担了。那就不要接着前面走，直接从当前值重新开始。
这等价于：左边界直接跳到当前位置。
所以这题虽然表面上像区间题，但真正高效的写法并不需要手动维护 left。
Why It Works
current 保存的是“必须以当前位置结尾”的最佳答案。
那么到 nums[i] 时：
- 如果前面的
current是有帮助的，就让它加上nums[i] - 如果前面的
current是拖累，就直接丢掉，从nums[i]重新开始
因为任何一个以 i 结尾的连续子数组，都只可能来自这两种情况，所以这个转移是完整的。
而 best 记录的是所有位置上 current 的最大值，也就是整个数组中的最大连续子数组和。
Code
def max_sub_array(nums: list[int]) -> int:
current = nums[0]
best = nums[0]
for i in range(1, len(nums)):
current = max(nums[i], current + nums[i])
best = max(best, current)
return bestComplexity
| Time | \(O(n)\) — 从左到右遍历一次数组 |
| Space | \(O(1)\) — 只维护了 current 和 best 两个变量 |
Takeaway
这题最容易卡住的地方，是一直盯着“区间左边界怎么移动”。但它真正适合维护的不是边界，而是“以当前位置结尾的最大和”。一旦前面的累计和变成负担，就直接从当前位置重新开始。这也是很多动态规划题里很常见的一种状态设计方式。
← Quiz