第一部分基石概念与核心思维1.1 什么是子数组在算法和数据结构中子数组是数组中的一个连续片段。对于数组arr子数组定义为arr[i...j]$0 \le i \le j n$包含从索引 $i$ 到 $j$ 的所有元素。空数组通常不被认为是子数组除非题目特别说明。区分子数组必须连续。子序列可以不连续只要保持相对顺序即可。1.2 为什么子数组问题适合 DP子数组问题的核心在于连续性。动态规划在解决子数组问题时通常采用“以某位置结尾”的视角。这是因为无后效性如果我们知道了“以 $i-1$ 结尾”的最优解那么“以 $i$ 结尾”的最优解通常只取决于前一个状态和当前元素arr[i]。枚举所有可能性遍历所有结尾位置就能覆盖所有子数组因为任何子数组都有唯一的结尾位置。1.3 DP 解题四步法针对子数组状态定义通常定义为dp[i]表示以第 i 个元素结尾的某个属性的最优值或计数。有时候需要多个状态来应对不同的情况例如正负、包含不包含等。转移方程分析dp[i]和dp[i-1]的关系。核心决策是延续前一个子数组还是重新开始。初始化通常是dp[0] base case根据arr[0]来定。答案通常不是dp[n-1]而是全局最优需要遍历所有dp[i]取最优或求和/计数。第二部分经典单状态模型2.1 最大子数组和 (Maximum Subarray Sum)问题给定整数数组nums找出一个具有最大和的连续子数组。经典解法Kadanes Algorithm。状态定义dp[i]以nums[i]结尾的最大子数组和。转移方程dp[i] max(nums[i], dp[i-1] nums[i])解释要么从i重新开始只取自己要么接在前一个最优子数组后面。初始化dp[0] nums[0]答案max(dp[0], dp[1], ..., dp[n-1])代码Pythonpythondef maxSubArray(nums): n len(nums) dp [0] * n dp[0] nums[0] res dp[0] for i in range(1, n): dp[i] max(nums[i], dp[i-1] nums[i]) res max(res, dp[i]) return res # 空间优化版O(1) 空间 def maxSubArray_opt(nums): cur nums[0] res cur for i in range(1, len(nums)): cur max(nums[i], cur nums[i]) res max(res, cur) return res变体最小子数组和将max改为min同理可得。2.2 最大子数组乘积 (Maximum Product Subarray)问题找出乘积最大的连续子数组数组包含负数。难点负数会使得最大变最小最小变最大。需要同时维护最大值和最小值。状态定义maxDP[i]以nums[i]结尾的最大乘积。minDP[i]以nums[i]结尾的最小乘积。转移方程textmaxDP[i] max(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i]) minDP[i] min(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])因为负数乘以最小值可能变成最大值负数乘以最大值可能变成最小值。初始化maxDP[0] minDP[0] nums[0]答案max(maxDP[i])over all i.代码pythondef maxProduct(nums): res maxDP minDP nums[0] for i in range(1, len(nums)): # 必须使用旧值所以先暂存 old_max maxDP maxDP max(nums[i], maxDP * nums[i], minDP * nums[i]) minDP min(nums[i], old_max * nums[i], minDP * nums[i]) res max(res, maxDP) return res第三部分计数类与可行性类3.1 统计以特定条件结尾的子数组数量问题给定数组统计有多少个子数组满足某种条件如和等于 k元素递增等。典型例题统计等差子数组的数量。问题给定数组返回所有长度 $\ge 2$ 的等差子数组的个数。状态定义dp[i]以nums[i]结尾的等差子数组的数量长度 $\ge 2$。转移如果nums[i] - nums[i-1] nums[i-1] - nums[i-2]那么以i-1结尾的所有等差子数组加上nums[i]仍然等差并且还能组成新的长度为 2 的数组[nums[i-1], nums[i]]。实际上更常见的递推是dp[i] dp[i-1] 1如果满足等差条件。答案sum(dp)。代码pythondef numberOfArithmeticSlices(nums): n len(nums) if n 3: return 0 dp [0] * n res 0 for i in range(2, n): if nums[i] - nums[i-1] nums[i-1] - nums[i-2]: dp[i] dp[i-1] 1 res dp[i] return res3.2 子数组和等于 K 的个数 (Subarray Sum Equals K)虽然前缀和 哈希表是经典解法但也可以用 DP 思想理解DP 视角dp[i]表示以 i 结尾的和为 K 的个数但需要枚举所有 j复杂度 O(N^2)。优化前缀和 Map。第四部分双状态模型与环形数组4.1 环形子数组最大和 (Maximum Sum Circular Subarray)问题数组首尾相连环形找最大子数组和。思路两种情况。最大子数组在中间正常 Kadane。最大子数组跨越了头尾相当于整个数组的和减去中间最小的子数组和。状态max_ending_hereKadanemin_ending_here求最小子数组和。注意如果所有数都是负数情况 2 会导致结果为空数组总和减最小0但空数组不允许需要特判。代码pythondef maxSubarraySumCircular(nums): total sum(nums) # Case 1: 普通最大子数组 max_cur max_so_far nums[0] # Case 2: 总和减去最小子数组 min_cur min_so_far nums[0] for i in range(1, len(nums)): max_cur max(nums[i], max_cur nums[i]) max_so_far max(max_so_far, max_cur) min_cur min(nums[i], min_cur nums[i]) min_so_far min(min_so_far, min_cur) # 如果全是负数总和减去最小值等于0但结果应该是最大负数 if max_so_far 0: return max_so_far return max(max_so_far, total - min_so_far)第五部分受限子数组与约束条件5.1 删除一次得到子数组最大和 (Maximum Subarray Sum with One Deletion)问题你可以从数组中删除一个元素或不删求最大子数组和。思路我们不知道删除的是哪个元素DP 需要记录“是否已经删除过”。状态定义dp0[i]以 i 结尾尚未删除任何元素的最大子数组和。dp1[i]以 i 结尾已经删除了一个元素的最大子数组和。转移dp0[i] max(nums[i], dp0[i-1] nums[i])(标准 Kadane)dp1[i] max(dp1[i-1] nums[i], dp0[i-1])解释已经删过一次的情况延续之前的删除状态加上当前元素。当前元素被删除所以结果是dp0[i-1]即之前没删过且以 i-1 结尾的最大值。初始化dp0[0] nums[0]dp1[0] -inf(因为只有一个元素时删除后数组为空通常题目要求至少一个元素)答案max(max(dp0), max(dp1))代码pythondef maximumSum(arr): n len(arr) dp0 [0]*n dp1 [0]*n dp0[0] arr[0] dp1[0] float(-inf) res dp0[0] for i in range(1, n): dp0[i] max(arr[i], dp0[i-1] arr[i]) dp1[i] max(dp1[i-1] arr[i], dp0[i-1]) # 后者表示删除当前i res max(res, dp0[i], dp1[i]) return res5.2 最长湍流子数组 (Longest Turbulent Subarray)问题子数组满足相邻数字的大小关系交替变化如 或 。思路维护两个状态记录当前上升和下降的长度。状态定义up[i]以 i 结尾且最后一步是上升arr[i] arr[i-1]的最长湍流子数组长度。down[i]以 i 结尾且最后一步是下降的最长长度。转移如果arr[i] arr[i-1]up[i] down[i-1] 1down[i] 1。如果arr[i] arr[i-1]down[i] up[i-1] 1up[i] 1。如果相等up[i] down[i] 1。初始化up[0] down[0] 1。答案max(up[i], down[i])。第六部分子数组与序列结合 (Subarray Subsequence)6.1 最长递增子数组 vs 最长递增子序列子数组连续。解法dp[i] dp[i-1] 1 if nums[i] nums[i-1] else 1。子序列不连续。解法O(N^2) 或 O(N log N) 贪心二分。6.2 最长公共子数组 (Longest Common Subarray) aka 最长重复子数组问题给定两个数组找出最长的公共子数组的长度。注意子数组要求连续这与最长公共子序列LCS不同。状态定义dp[i][j]以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度。转移textif nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 0答案max(dp[i][j])。代码pythondef findLength(nums1, nums2): m, n len(nums1), len(nums2) dp [[0]*(n1) for _ in range(m1)] res 0 for i in range(1, m1): for j in range(1, n1): if nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1 res max(res, dp[i][j]) return res第七部分进阶优化——单调队列与滑动窗口当 DP 转移涉及到区间最值时单纯遍历会超时O(N^2) 或 O(N*K)。此时需要单调队列优化。7.1 限制长度的最大子数组和问题求长度不超过 K 的最大子数组和。解法前缀和 单调队列维护最小值。7.2 最长连续子数组使得绝对差不超过限制问题返回最长子数组的长度使得子数组的最大值和最小值的差 limit。解法滑动窗口 单调队列维护最大最小值。7.3 分割数组的最大值 (Split Array Largest Sum)虽然这是二分贪心经典题但也可以用 DP 做dp[i][k] 将前 i 个元素分成 k 段的最小化最大和。转移dp[i][k] min( max(dp[j][k-1], sum(j1...i)) )。优化使用二分答案更常见。第八部分多维状态与复杂模型8.1 子数组按位或操作问题统计数组的所有子数组中按位或的结果有多少种不同的值。DP 技巧dp[i]存储以 i 结尾的所有子数组的 OR 值集合。因为 OR 操作的性质集合大小不会超过 32或 log(maxValue)所以复杂度 O(N * logC)。8.2 子数组最小值的乘积之和 (Sum of Subarray Minimums)问题求所有子数组的最小值的和。解法单调栈找到每个元素作为最小值的作用范围左右边界然后计算贡献。虽然这不是传统 DP但涉及到“子数组”的统计是 DP 思维的延伸。公式ans sum( arr[i] * (i - left[i]) * (right[i] - i) )第九部分实战演练——综合例题分析例题 1最长斐波那契子序列的长度 (Longest Fibonacci Subsequence)虽然这是子序列问题但其 DP 状态设计非常精妙可以作为子数组问题的延伸。例题 2最多删除一个元素的最长递增子数组问题最多删除一个元素求最长严格递增子数组的长度。思路预处理left[i]以 i 结尾的最长递增子数组长度。预处理right[i]以 i 开头的最长递增子数组长度。答案 max( left[i], right[i], left[i-1] 1 right[i1] if nums[i1] nums[i-1] )。这展示了如何利用“前后缀”预处理来处理删除操作。例题 3最大子数组和使得子数组内不包含相邻元素这其实是“打家劫舍”变体但如果是子数组且连续实际上如果要求子数组内不能取相邻元素就变成了求一个子序列不连续因此通常使用序列 DP。第十部分总结与解题思维10.1 子数组 DP 的常见模式最值类定义dp[i]为“以 i 结尾的最优值”。转移dp[i] f(arr[i], dp[i-1])。代表题最大子数组和、最长湍流子数组。计数类定义dp[i]为“以 i 结尾的满足条件的子数组个数”。转移dp[i] dp[i-1] 1当满足连续性条件时。代表题等差子数组计数。双状态类处理正负/删除/方向定义dp0[i]和dp1[i]表示不同情况下的值。代表题乘积最大子数组、一次删除的最大和、湍流子数组。二维类两个数组/多维度定义dp[i][j]处理公共子数组或路径问题。代表题最长公共子数组。10.2 面试与竞赛中的注意事项空间优化大部分一维 DP 可以优化到 O(1) 空间只保留前一个状态。负数陷阱在最大/最小乘积类问题中记得同时维护最小和最大。空数组注意题目是否允许空数组通常不允许。环形数组考虑“总-最小”或者复制数组拼接。单调队列优化当 DP 转移涉及“前 K 个的最值”时考虑单调队列。10.3 刷题路线建议基础最大子数组和、最大子数组乘积。计数等差子数组数量、湍流子数组。约束删除一个元素的最大和、环形数组。二维最长公共子数组。进阶单调队列优化如 1425. 带限制的子序列和。
DP 子数组模型：从入门到精通
第一部分基石概念与核心思维1.1 什么是子数组在算法和数据结构中子数组是数组中的一个连续片段。对于数组arr子数组定义为arr[i...j]$0 \le i \le j n$包含从索引 $i$ 到 $j$ 的所有元素。空数组通常不被认为是子数组除非题目特别说明。区分子数组必须连续。子序列可以不连续只要保持相对顺序即可。1.2 为什么子数组问题适合 DP子数组问题的核心在于连续性。动态规划在解决子数组问题时通常采用“以某位置结尾”的视角。这是因为无后效性如果我们知道了“以 $i-1$ 结尾”的最优解那么“以 $i$ 结尾”的最优解通常只取决于前一个状态和当前元素arr[i]。枚举所有可能性遍历所有结尾位置就能覆盖所有子数组因为任何子数组都有唯一的结尾位置。1.3 DP 解题四步法针对子数组状态定义通常定义为dp[i]表示以第 i 个元素结尾的某个属性的最优值或计数。有时候需要多个状态来应对不同的情况例如正负、包含不包含等。转移方程分析dp[i]和dp[i-1]的关系。核心决策是延续前一个子数组还是重新开始。初始化通常是dp[0] base case根据arr[0]来定。答案通常不是dp[n-1]而是全局最优需要遍历所有dp[i]取最优或求和/计数。第二部分经典单状态模型2.1 最大子数组和 (Maximum Subarray Sum)问题给定整数数组nums找出一个具有最大和的连续子数组。经典解法Kadanes Algorithm。状态定义dp[i]以nums[i]结尾的最大子数组和。转移方程dp[i] max(nums[i], dp[i-1] nums[i])解释要么从i重新开始只取自己要么接在前一个最优子数组后面。初始化dp[0] nums[0]答案max(dp[0], dp[1], ..., dp[n-1])代码Pythonpythondef maxSubArray(nums): n len(nums) dp [0] * n dp[0] nums[0] res dp[0] for i in range(1, n): dp[i] max(nums[i], dp[i-1] nums[i]) res max(res, dp[i]) return res # 空间优化版O(1) 空间 def maxSubArray_opt(nums): cur nums[0] res cur for i in range(1, len(nums)): cur max(nums[i], cur nums[i]) res max(res, cur) return res变体最小子数组和将max改为min同理可得。2.2 最大子数组乘积 (Maximum Product Subarray)问题找出乘积最大的连续子数组数组包含负数。难点负数会使得最大变最小最小变最大。需要同时维护最大值和最小值。状态定义maxDP[i]以nums[i]结尾的最大乘积。minDP[i]以nums[i]结尾的最小乘积。转移方程textmaxDP[i] max(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i]) minDP[i] min(nums[i], maxDP[i-1] * nums[i], minDP[i-1] * nums[i])因为负数乘以最小值可能变成最大值负数乘以最大值可能变成最小值。初始化maxDP[0] minDP[0] nums[0]答案max(maxDP[i])over all i.代码pythondef maxProduct(nums): res maxDP minDP nums[0] for i in range(1, len(nums)): # 必须使用旧值所以先暂存 old_max maxDP maxDP max(nums[i], maxDP * nums[i], minDP * nums[i]) minDP min(nums[i], old_max * nums[i], minDP * nums[i]) res max(res, maxDP) return res第三部分计数类与可行性类3.1 统计以特定条件结尾的子数组数量问题给定数组统计有多少个子数组满足某种条件如和等于 k元素递增等。典型例题统计等差子数组的数量。问题给定数组返回所有长度 $\ge 2$ 的等差子数组的个数。状态定义dp[i]以nums[i]结尾的等差子数组的数量长度 $\ge 2$。转移如果nums[i] - nums[i-1] nums[i-1] - nums[i-2]那么以i-1结尾的所有等差子数组加上nums[i]仍然等差并且还能组成新的长度为 2 的数组[nums[i-1], nums[i]]。实际上更常见的递推是dp[i] dp[i-1] 1如果满足等差条件。答案sum(dp)。代码pythondef numberOfArithmeticSlices(nums): n len(nums) if n 3: return 0 dp [0] * n res 0 for i in range(2, n): if nums[i] - nums[i-1] nums[i-1] - nums[i-2]: dp[i] dp[i-1] 1 res dp[i] return res3.2 子数组和等于 K 的个数 (Subarray Sum Equals K)虽然前缀和 哈希表是经典解法但也可以用 DP 思想理解DP 视角dp[i]表示以 i 结尾的和为 K 的个数但需要枚举所有 j复杂度 O(N^2)。优化前缀和 Map。第四部分双状态模型与环形数组4.1 环形子数组最大和 (Maximum Sum Circular Subarray)问题数组首尾相连环形找最大子数组和。思路两种情况。最大子数组在中间正常 Kadane。最大子数组跨越了头尾相当于整个数组的和减去中间最小的子数组和。状态max_ending_hereKadanemin_ending_here求最小子数组和。注意如果所有数都是负数情况 2 会导致结果为空数组总和减最小0但空数组不允许需要特判。代码pythondef maxSubarraySumCircular(nums): total sum(nums) # Case 1: 普通最大子数组 max_cur max_so_far nums[0] # Case 2: 总和减去最小子数组 min_cur min_so_far nums[0] for i in range(1, len(nums)): max_cur max(nums[i], max_cur nums[i]) max_so_far max(max_so_far, max_cur) min_cur min(nums[i], min_cur nums[i]) min_so_far min(min_so_far, min_cur) # 如果全是负数总和减去最小值等于0但结果应该是最大负数 if max_so_far 0: return max_so_far return max(max_so_far, total - min_so_far)第五部分受限子数组与约束条件5.1 删除一次得到子数组最大和 (Maximum Subarray Sum with One Deletion)问题你可以从数组中删除一个元素或不删求最大子数组和。思路我们不知道删除的是哪个元素DP 需要记录“是否已经删除过”。状态定义dp0[i]以 i 结尾尚未删除任何元素的最大子数组和。dp1[i]以 i 结尾已经删除了一个元素的最大子数组和。转移dp0[i] max(nums[i], dp0[i-1] nums[i])(标准 Kadane)dp1[i] max(dp1[i-1] nums[i], dp0[i-1])解释已经删过一次的情况延续之前的删除状态加上当前元素。当前元素被删除所以结果是dp0[i-1]即之前没删过且以 i-1 结尾的最大值。初始化dp0[0] nums[0]dp1[0] -inf(因为只有一个元素时删除后数组为空通常题目要求至少一个元素)答案max(max(dp0), max(dp1))代码pythondef maximumSum(arr): n len(arr) dp0 [0]*n dp1 [0]*n dp0[0] arr[0] dp1[0] float(-inf) res dp0[0] for i in range(1, n): dp0[i] max(arr[i], dp0[i-1] arr[i]) dp1[i] max(dp1[i-1] arr[i], dp0[i-1]) # 后者表示删除当前i res max(res, dp0[i], dp1[i]) return res5.2 最长湍流子数组 (Longest Turbulent Subarray)问题子数组满足相邻数字的大小关系交替变化如 或 。思路维护两个状态记录当前上升和下降的长度。状态定义up[i]以 i 结尾且最后一步是上升arr[i] arr[i-1]的最长湍流子数组长度。down[i]以 i 结尾且最后一步是下降的最长长度。转移如果arr[i] arr[i-1]up[i] down[i-1] 1down[i] 1。如果arr[i] arr[i-1]down[i] up[i-1] 1up[i] 1。如果相等up[i] down[i] 1。初始化up[0] down[0] 1。答案max(up[i], down[i])。第六部分子数组与序列结合 (Subarray Subsequence)6.1 最长递增子数组 vs 最长递增子序列子数组连续。解法dp[i] dp[i-1] 1 if nums[i] nums[i-1] else 1。子序列不连续。解法O(N^2) 或 O(N log N) 贪心二分。6.2 最长公共子数组 (Longest Common Subarray) aka 最长重复子数组问题给定两个数组找出最长的公共子数组的长度。注意子数组要求连续这与最长公共子序列LCS不同。状态定义dp[i][j]以nums1[i-1]和nums2[j-1]结尾的最长公共子数组长度。转移textif nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 0答案max(dp[i][j])。代码pythondef findLength(nums1, nums2): m, n len(nums1), len(nums2) dp [[0]*(n1) for _ in range(m1)] res 0 for i in range(1, m1): for j in range(1, n1): if nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1 res max(res, dp[i][j]) return res第七部分进阶优化——单调队列与滑动窗口当 DP 转移涉及到区间最值时单纯遍历会超时O(N^2) 或 O(N*K)。此时需要单调队列优化。7.1 限制长度的最大子数组和问题求长度不超过 K 的最大子数组和。解法前缀和 单调队列维护最小值。7.2 最长连续子数组使得绝对差不超过限制问题返回最长子数组的长度使得子数组的最大值和最小值的差 limit。解法滑动窗口 单调队列维护最大最小值。7.3 分割数组的最大值 (Split Array Largest Sum)虽然这是二分贪心经典题但也可以用 DP 做dp[i][k] 将前 i 个元素分成 k 段的最小化最大和。转移dp[i][k] min( max(dp[j][k-1], sum(j1...i)) )。优化使用二分答案更常见。第八部分多维状态与复杂模型8.1 子数组按位或操作问题统计数组的所有子数组中按位或的结果有多少种不同的值。DP 技巧dp[i]存储以 i 结尾的所有子数组的 OR 值集合。因为 OR 操作的性质集合大小不会超过 32或 log(maxValue)所以复杂度 O(N * logC)。8.2 子数组最小值的乘积之和 (Sum of Subarray Minimums)问题求所有子数组的最小值的和。解法单调栈找到每个元素作为最小值的作用范围左右边界然后计算贡献。虽然这不是传统 DP但涉及到“子数组”的统计是 DP 思维的延伸。公式ans sum( arr[i] * (i - left[i]) * (right[i] - i) )第九部分实战演练——综合例题分析例题 1最长斐波那契子序列的长度 (Longest Fibonacci Subsequence)虽然这是子序列问题但其 DP 状态设计非常精妙可以作为子数组问题的延伸。例题 2最多删除一个元素的最长递增子数组问题最多删除一个元素求最长严格递增子数组的长度。思路预处理left[i]以 i 结尾的最长递增子数组长度。预处理right[i]以 i 开头的最长递增子数组长度。答案 max( left[i], right[i], left[i-1] 1 right[i1] if nums[i1] nums[i-1] )。这展示了如何利用“前后缀”预处理来处理删除操作。例题 3最大子数组和使得子数组内不包含相邻元素这其实是“打家劫舍”变体但如果是子数组且连续实际上如果要求子数组内不能取相邻元素就变成了求一个子序列不连续因此通常使用序列 DP。第十部分总结与解题思维10.1 子数组 DP 的常见模式最值类定义dp[i]为“以 i 结尾的最优值”。转移dp[i] f(arr[i], dp[i-1])。代表题最大子数组和、最长湍流子数组。计数类定义dp[i]为“以 i 结尾的满足条件的子数组个数”。转移dp[i] dp[i-1] 1当满足连续性条件时。代表题等差子数组计数。双状态类处理正负/删除/方向定义dp0[i]和dp1[i]表示不同情况下的值。代表题乘积最大子数组、一次删除的最大和、湍流子数组。二维类两个数组/多维度定义dp[i][j]处理公共子数组或路径问题。代表题最长公共子数组。10.2 面试与竞赛中的注意事项空间优化大部分一维 DP 可以优化到 O(1) 空间只保留前一个状态。负数陷阱在最大/最小乘积类问题中记得同时维护最小和最大。空数组注意题目是否允许空数组通常不允许。环形数组考虑“总-最小”或者复制数组拼接。单调队列优化当 DP 转移涉及“前 K 个的最值”时考虑单调队列。10.3 刷题路线建议基础最大子数组和、最大子数组乘积。计数等差子数组数量、湍流子数组。约束删除一个元素的最大和、环形数组。二维最长公共子数组。进阶单调队列优化如 1425. 带限制的子序列和。
