第 28 站 · 动态规划

状态机与连续序列

以 i 结尾的状态：同时记最大和最小时间 O(n) · 空间 O(1)

周赛难度分难度分 1602–难度分 1799· 中位难度分 1786（5/6 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 28 站 · 6 题

先学: 动规入门
学完去: 股票买卖
面试频次: 1 家公司考过 · 面经出现 1 次TikTok / ByteDance 1

先做这道

LC 152乘积最大子数组中等

卡住再看

负数会交换最大和最小乘积，训练同时保留两种状态及零的重置。

要点

状态定义成「以 i 结尾」，连续子数组的转移就只有两种：接在前一段后面，或者从 i 重新开始。
乘法遇到负数时最大会变成最小，所以要同时维护最大和最小两个状态。
状态机 DP 就是给每个位置多设几个状态（持有 / 不持有、上一个选没选），把状态之间的每条转移都写出来。

易错点

先更新了 hi 再用新的 hi 去算 lo，用到的是同一轮已经改过的值。
答案初始化成 0，全是负数的数组就会出错。
最大子数组和（Kadane）的转移是 cur = max(x, cur + x)，不要漏掉「重新开始」这一项。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

状态机 DP · 含冷冻期的股票买卖

价格 1, 2, 3, 0, 2，卖出后要冷冻一天，最大利润是多少？

换个输入

价格

1第 0 天

2第 1 天

3第 2 天

0第 3 天

2第 4 天

持有

·持有[0]

·持有[1]

·持有[2]

·持有[3]

·持有[4]

冷冻

·冷冻[0]

·冷冻[1]

·冷冻[2]

·冷冻[3]

·冷冻[4]

空仓

·空仓[0]

·空仓[1]

·空仓[2]

·空仓[3]

·空仓[4]

当前处理已发现 / 已计算答案

第几天: —
最大利润: 0

每天结束时处在三种状态之一：持有股票、刚卖出（明天冷冻不能买）、空仓可买。每列只由前一列算出。

速度

步骤 1 / 7

始终成立每天的三个状态只由前一天的三个状态转移而来：hold → cool（卖），free → hold（买），cool → free（等一天）。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 152。

Python

def max_product(nums: list[int]) -> int:
    """Largest product of a non-empty contiguous subarray."""
    hi = lo = best = nums[0]  # max and min product of a subarray ending here
    for x in nums[1:]:
        cand = (x, hi * x, lo * x)  # restart, or extend; a negative x swaps max and min
        hi, lo = max(cand), min(cand)
        best = max(best, hi)
    return best

C++

// Largest product of a non-empty contiguous subarray.
long long maxProduct(const vector<int>& nums) {
    long long hi = nums[0], lo = nums[0], best = nums[0];  // max and min product ending here
    for (size_t i = 1; i < nums.size(); i++) {
        long long x = nums[i];
        long long a = hi * x, b = lo * x;  // a negative x swaps max and min
        hi = max({x, a, b});  // restart, or extend
        lo = min({x, a, b});
        best = max(best, hi);
    }
    return best;
}

Java

class Solution {
    // Largest product of a non-empty contiguous subarray.
    long maxProduct(int[] nums) {
        long hi = nums[0], lo = nums[0], best = nums[0]; // max and min product ending here
        for (int i = 1; i < nums.length; i++) {
            long x = nums[i], a = hi * x, b = lo * x; // a negative x swaps max and min
            hi = Math.max(x, Math.max(a, b)); // restart, or extend
            lo = Math.min(x, Math.min(a, b));
            best = Math.max(best, hi);
        }
        return best;
    }
}

// maxProduct returns the largest product of a non-empty contiguous subarray.
func maxProduct(nums []int) int {
	hi, lo, best := nums[0], nums[0], nums[0] // max and min product ending here
	for _, x := range nums[1:] {
		a, b := hi*x, lo*x                  // a negative x swaps max and min
		hi, lo = max(x, a, b), min(x, a, b) // restart, or extend
		best = max(best, hi)
	}
	return best
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

环形子数组：总和减去最小子数组时间 O(n) · 空间 O(1)

数组首尾相连时，最大子数组要么不跨界（普通 Kadane），要么跨界：跨界的那段等于「总和减去中间一段」，中间那段取最小子数组和。全为负数时「总和 − 最小」对应空数组，要退回普通 Kadane 的结果。LC 918 环形子数组的最大和。

Python

def max_circular_subarray(nums: list[int]) -> int:
    """Largest sum of a non-empty subarray when the array wraps around (LC 918)."""
    best_max = cur_max = best_min = cur_min = total = nums[0]
    for x in nums[1:]:
        cur_max = max(x, cur_max + x)  # Kadane for the largest subarray...
        best_max = max(best_max, cur_max)
        cur_min = min(x, cur_min + x)  # ...and for the smallest
        best_min = min(best_min, cur_min)
        total += x
    # Wrapping = everything but a middle part. All negative: that would be empty, so don't.
    return max(best_max, total - best_min) if best_max > 0 else best_max

C++

// Largest sum of a non-empty subarray when the array wraps around (LC 918).
int maxCircularSubarray(const vector<int>& nums) {
    int bestMax = nums[0], curMax = nums[0], bestMin = nums[0], curMin = nums[0], total = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        int x = nums[i];
        curMax = max(x, curMax + x);  // Kadane for the largest subarray...
        bestMax = max(bestMax, curMax);
        curMin = min(x, curMin + x);  // ...and for the smallest
        bestMin = min(bestMin, curMin);
        total += x;
    }
    // Wrapping = everything but a middle part. All negative: that would be empty, so don't.
    return bestMax > 0 ? max(bestMax, total - bestMin) : bestMax;
}

Java

class Solution {
    // Largest sum of a non-empty subarray when the array wraps around (LC 918).
    int maxCircularSubarray(int[] nums) {
        int bestMax = nums[0], curMax = nums[0], bestMin = nums[0], curMin = nums[0], total = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            curMax = Math.max(x, curMax + x); // Kadane for the largest subarray...
            bestMax = Math.max(bestMax, curMax);
            curMin = Math.min(x, curMin + x); // ...and for the smallest
            bestMin = Math.min(bestMin, curMin);
            total += x;
        }
        // Wrapping = everything but a middle part. All negative: that would be empty, so don't.
        return bestMax > 0 ? Math.max(bestMax, total - bestMin) : bestMax;
    }
}

// maxCircularSubarray returns the largest sum of a non-empty subarray when the array wraps (LC 918).
func maxCircularSubarray(nums []int) int {
	bestMax, curMax, bestMin, curMin, total := nums[0], nums[0], nums[0], nums[0], nums[0]
	for _, x := range nums[1:] {
		curMax = max(x, curMax+x) // Kadane for the largest subarray...
		bestMax = max(bestMax, curMax)
		curMin = min(x, curMin+x) // ...and for the smallest
		bestMin = min(bestMin, curMin)
		total += x
	}
	// Wrapping = everything but a middle part. All negative: that would be empty, so don't.
	if bestMax > 0 {
		return max(bestMax, total-bestMin)
	}
	return bestMax
}

两个状态：还没删 / 已经删了一个时间 O(n) · 空间 O(1)

允许「最多删一个 / 翻转一次 / 跳过一次」的子数组问题，给以 i 结尾的状态加一维：keep 是还没用掉机会，dropped 是已经用掉。dropped 要么是删掉 x 本身（接上旧的 keep），要么是早删过、现在接上 x。LC 1186 删除一次得到子数组最大和；LC 1911、LC 926 也是这类两三个状态互相转移。

Python

def max_sum_one_deletion(arr: list[int]) -> int:
    """Largest sum of a non-empty subarray with at most one element deleted (LC 1186)."""
    keep = best = arr[0]  # keep: best sum ending here with nothing deleted
    dropped = float("-inf")  # best sum ending here with one element deleted
    for x in arr[1:]:
        dropped = max(keep, dropped + x)  # delete x (old keep), or extend an earlier deletion
        keep = max(x, keep + x)
        best = max(best, keep, dropped)
    return best

C++

// Largest sum of a non-empty subarray with at most one element deleted (LC 1186).
long long maxSumOneDeletion(const vector<int>& arr) {
    long long keep = arr[0], best = arr[0];  // keep: best sum ending here with nothing deleted
    long long dropped = LLONG_MIN / 2;  // best sum ending here with one element deleted
    for (size_t i = 1; i < arr.size(); i++) {
        long long x = arr[i];
        dropped = max(keep, dropped + x);  // delete x (old keep), or extend an earlier deletion
        keep = max(x, keep + x);
        best = max({best, keep, dropped});
    }
    return best;
}

Java

class Solution {
    // Largest sum of a non-empty subarray with at most one element deleted (LC 1186).
    long maxSumOneDeletion(int[] arr) {
        long keep = arr[0], best = arr[0]; // keep: best sum ending here with nothing deleted
        long dropped = Long.MIN_VALUE / 2; // best sum ending here with one element deleted
        for (int i = 1; i < arr.length; i++) {
            long x = arr[i];
            dropped = Math.max(keep, dropped + x); // delete x (old keep), or extend an earlier deletion
            keep = Math.max(x, keep + x);
            best = Math.max(best, Math.max(keep, dropped));
        }
        return best;
    }
}

// maxSumOneDeletion returns the largest subarray sum with at most one element deleted (LC 1186).
func maxSumOneDeletion(arr []int) int {
	keep, best := arr[0], arr[0] // keep: best sum ending here with nothing deleted
	dropped := -1 << 60 // best sum ending here with one element deleted
	for _, x := range arr[1:] {
		dropped = max(keep, dropped+x) // delete x (old keep), or extend an earlier deletion
		keep = max(x, keep+x)
		best = max(best, keep, dropped)
	}
	return best
}

为什么对

以 i 结尾的连续子数组只有两种：只含 nums[i]，或者是以 i−1 结尾的某个子数组再接上 nums[i]，所以「重新开始」和「延续」覆盖了全部情况。
乘以负数会让最大变最小、最小变最大，所以以 i 结尾的最大乘积只可能是 x、hi·x、lo·x 之一，同时维护 hi 和 lo 才完整。
答案是所有位置 hi 的最大值，而不是最后一个 hi，因为最优子数组可以在任意位置结束。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文

连续子数组的题，我把状态定义成以 i 结尾，这样只有两种转移：接在前一个后面，或者从 i 重新开始。最大乘积子数组里，负数会让最大值和最小值互换，所以我同时维护以 i 结尾的最大乘积和最小乘积，新值从 x、hi 乘 x、lo 乘 x 三个候选里取。答案是每个位置 hi 的最大值。一遍扫描，O(n) 时间、O(1) 空间。

English

For contiguous subarray problems I define the state as ending at i, which leaves two transitions: extend the previous run or restart at i. In maximum product subarray a negative number swaps the largest and smallest products, so I keep both the max and the min ending at i, and each new value comes from x, hi times x or lo times x. The answer is the largest hi seen at any position. It is one pass, O(n) time and O(1) space.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）

以 i 结尾的连续子数组只有两种：只含 nums[i]，或者是以 i−1 结尾的某个子数组再接上 nums[i]，所以「重新开始」和「延续」覆盖了全部情况。
乘以负数会让最大变最小、最小变最大，所以以 i 结尾的最大乘积只可能是 x、hi·x、lo·x 之一，同时维护 hi 和 lo 才完整。
答案是所有位置 hi 的最大值，而不是最后一个 hi，因为最优子数组可以在任意位置结束。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

分档练习

本站在 500 路里的 6 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

核心 5

#	题目	一句话思路	难度分
152	乘积最大子数组	负数会交换最大和最小乘积，训练同时保留两种状态及零的重置。
918	环形子数组的最大和	把跨越尾首的最大和转为总和减最小子数组，单独处理全负输入。	难度分 1777
1911	最大交替子序列和	按所选元素个数的奇偶维护加减状态，避免把原数组下标当成符号依据。	难度分 1786
926	将字符串翻转到单调递增	把单调二进制串分成全零和已进入一段两种阶段，比较前缀计数解法。	难度分 1602
1653	使字符串平衡的最少删除次数	在保持字符顺序的前提下选择删除当前a或此前b，练习线性状态压缩。	难度分 1794

进阶 1

#	题目	一句话思路	难度分
1186	删除一次得到子数组最大和	用尚未删除和已经删除两个状态表达一次机会，保证结果子数组非空。	难度分 1799

本站 OA 真题 14

Calculate Max Quality ScoreAmazon
Calculate Maximum Quality ScoreAmazon
Get Number of Perfect PackagingAmazon
Maximize Protected City PopulationAmazon
Minimum Preparation Time for Two HandlersAmazon
Minimum Value Calculation by Replacing '!' in a Binary StringAmazon
Trader Joe TradesAmazon
Maximum Sum with TilesMicrosoft
Coloring HousesSnowflake
Efficient DeploymentsSnowflake

全部 14 道

先做这道

要点

易错点

看动画

模板

常见变体

为什么对

30 秒口述稿

自评一下

小测

模板练习

分档练习

核心 5

进阶 1

本站 OA 真题 14