15 贪心 先说出「局部最优不毁全局」的那个性质，再动手

先记住这一句

贪心的代码短得可疑：通常就是一个循环加一两个变量。难度全在为什么对。面试里的标准动作是三步：说出贪心性质 → 自己举一个反例试着推翻它 → 再写代码。跳过前两步直接写，写对了也说不清，写错了更找不到原因。

本章第一题 53 Maximum Subarray 恰好站在贪心和 DP 的边界上：cur = max(x, cur + x) 既能读成「要不要另起炉灶」的贪心决策，也能读成 dp[i] = max(nums[i], dp[i-1] + nums[i]) 的状态转移。两种说法在面试里都对，能同时说出来最好。

看到什么，想到本章

可默写的那几行

■ 【骨架】 不变，闭着眼默写　■ 【插槽】 随题变化，写题前先问自己填什么

def max_subarray(nums):
    best = cur = nums[0]                    # 【骨架】cur = 以当前元素结尾的最优值
    for x in nums[1:]:                      # 【骨架】
        cur = max(x, cur + x)               # 【插槽】决策:另起炉灶,还是接着上一段
        best = max(best, cur)               # 【插槽】答案:全局最优 / 最后一项 / 计数
    return best

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}  # 【插槽】贪心依据:每个元素最后出现在哪
    out, start, end = [], 0, 0
    for i, c in enumerate(s):               # 【骨架】
        end = max(end, last[c])             # 【骨架】当前段被迫延伸到这里
        if i == end:                        # 【骨架】走到边界了,收一段
            out.append(end - start + 1)     # 【插槽】答案:段长 / 段数 / 段的内容
            start = i + 1                   # 【骨架】
    return out

从建直觉到扭模板

会写不等于不翻车

1. 不证明就贪——先说清「为什么局部最优不会毁掉全局」。说不出来时，把它当 DP 写，复杂度差一点但不会错。面试官问「你怎么知道这样贪是对的」时答不上来，比写慢更致命。
2. Kadane 的初值——best = cur = 0 在全负数组上会返回 0（相当于允许空子数组）。题目要求非空时必须用 nums[0] 起手。
3. 55 和 45 混用骨架——「能否到达」维护一个 reach 就够；「最少几步」必须分层，用 curEnd / farthest 两个变量。把 45 写成 55 的样子会得到步数偏小的错误答案。
4. 134 只判总量——总量够只说明有解，不告诉你从哪起步。两个结论要一起用。
5. 对「找零钱」类问题贪心——只有在面额构成特定体系（如 1/5/10/25）时贪心才对。LeetCode 的 322 面额是任意的，必须 DP——见 §2 分流条件。

自测 · 30 秒识别模式