动态规划解决子数组问题的7种经典方法

## 1. 动态规划与子数组问题概述 子数组问题是算法面试中的高频考点，也是动态规划技术的经典应用场景。所谓子数组，指的是数组中连续的一个或多个元素组成的序列。与子序列不同，子数组要求元素在原数组中的位置必须连续。这类问题往往要求我们在O(n)时间复杂度内完成计算，这正是动态规划大显身手的地方。 我在刷题和面试辅导过程中发现，90%的子数组问题都可以用动态规划思路解决。关键在于定义好状态转移方程，并处理好边界条件。下面我将通过7个典型问题，带你掌握动态规划解决子数组问题的核心套路。这些题目全部来自力扣热门题库，也是大厂面试的常考题。 ## 2. 最大子数组和问题 ### 2.1 问题描述与暴力解法 给定一个整数数组nums，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 例如： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为6。 暴力解法很容易想到：枚举所有可能的子数组，计算它们的和，然后取最大值。这种方法的时间复杂度是O(n²)，在n较大时（比如n=10^5）完全无法接受。 ### 2.2 动态规划解法 定义dp[i]表示以第i个元素结尾的子数组的最大和。状态转移方程为： dp[i] = max(nums[i], dp[i-1] + nums[i]) 这个方程的意思是：对于第i个元素，要么单独作为一个子数组，要么接在前面的子数组后面。我们取这两种情况中的较大值。 实现代码（Python）： ```python def maxSubArray(nums): dp = [0] * len(nums) dp[0] = nums[0] for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i-1] + nums[i]) return max(dp)

2.3 空间优化技巧

观察状态转移方程可以发现，dp[i]只依赖于dp[i-1]，因此可以用一个变量代替整个dp数组，将空间复杂度从O(n)降到O(1)：

def maxSubArray(nums): max_sum = current_sum = nums[0] for num in nums[1:]: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum

注意：初始化时max_sum和current_sum都应该设为nums[0]，而不是0，因为子数组至少要包含一个元素。

3. 环形子数组的最大和

3.1 问题描述

给定一个环形数组nums，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

环形数组意味着数组的首尾相连。例如： 输入：nums = [5,-3,5] 输出：10 解释：子数组 [5,5]（首尾相连）的和最大，为10。

3.2 解题思路

这个问题有两种情况：

1. 最大和子数组不跨越数组首尾（即普通的最大子数组和问题）
2. 最大和子数组跨越了数组首尾

对于第二种情况，可以转化为求数组总和减去最小子数组和。因此最终结果为： max(普通最大子数组和，数组总和 - 普通最小子数组和)

但需要注意一个特殊情况：如果所有数都是负数，那么数组总和 - 最小子数组和 = 0（最小子数组和就是整个数组），但实际结果应该是最大的那个负数。

3.3 实现代码

def maxSubarraySumCircular(nums): total = sum(nums) # 计算普通最大子数组和 max_sum = current_max = nums[0] for num in nums[1:]: current_max = max(num, current_max + num) max_sum = max(max_sum, current_max) # 计算普通最小子数组和 min_sum = current_min = nums[0] for num in nums[1:]: current_min = min(num, current_min + num) min_sum = min(min_sum, current_min) # 处理全负数的情况 if max_sum < 0: return max_sum return max(max_sum, total - min_sum)

4. 乘积最大子数组

4.1 问题描述

给你一个整数数组nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

例如： 输入：nums = [2,3,-2,4] 输出：6 解释：子数组 [2,3] 有最大乘积6。

4.2 解题思路

与求和不同，乘积有以下特点：

1. 当前元素可能使乘积变大或变小（取决于正负）
2. 负数乘以负数会变成正数

因此需要同时维护当前的最大乘积和最小乘积：

• max_dp[i] = max(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])
• min_dp[i] = min(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])

4.3 实现代码

def maxProduct(nums): if not nums: return 0 max_prod = min_prod = result = nums[0] for num in nums[1:]: candidates = (num, max_prod * num, min_prod * num) max_prod = max(candidates) min_prod = min(candidates) result = max(result, max_prod) return result

5. 乘积为正数的最长子数组长度

5.1 问题描述

给你一个整数数组nums，请你求出乘积为正数的最长子数组的长度。

例如： 输入：nums = [1,-2,-3,4] 输出：4 解释：整个数组的乘积是24，是正数，所以最长长度为4。

5.2 解题思路

需要维护两个状态：

1. positive：以当前元素结尾的乘积为正数的最长子数组长度
2. negative：以当前元素结尾的乘积为负数的最长子数组长度

状态转移规则：

• 如果nums[i] > 0：
  • positive = positive + 1
  • negative = negative + 1（如果negative > 0）
• 如果nums[i] < 0：
  • positive = negative + 1（如果negative > 0）
  • negative = positive + 1
• 如果nums[i] == 0：
  • positive = negative = 0

5.3 实现代码

def getMaxLen(nums): positive = negative = max_len = 0 for num in nums: if num > 0: positive += 1 negative = negative + 1 if negative > 0 else 0 elif num < 0: new_positive = negative + 1 if negative > 0 else 0 new_negative = positive + 1 positive, negative = new_positive, new_negative else: positive = negative = 0 max_len = max(max_len, positive) return max_len

6. 最长湍流子数组

6.1 问题描述

给定一个整数数组arr，返回arr的最大湍流子数组的长度。

湍流子数组定义为：比较符号在子数组的每对相邻元素之间翻转。

• 当arr[i] > arr[i+1]时，下一对应该是arr[i] < arr[i+1]
• 反之亦然

例如： 输入：arr = [9,4,2,10,7,8,8,1,9] 输出：5 解释：最长的湍流子数组是[4,2,10,7,8]

6.2 解题思路

定义两个状态：

1. up：以arr[i]结尾，最后是上升的最长湍流子数组长度
2. down：以arr[i]结尾，最后是下降的最长湍流子数组长度

状态转移：

• 如果arr[i] > arr[i-1]：
  • up = down + 1
  • down = 1
• 如果arr[i] < arr[i-1]：
  • down = up + 1
  • up = 1
• 如果相等：
  • up = down = 1

6.3 实现代码

def maxTurbulenceSize(arr): if len(arr) < 2: return len(arr) up = down = result = 1 for i in range(1, len(arr)): if arr[i] > arr[i-1]: up = down + 1 down = 1 elif arr[i] < arr[i-1]: down = up + 1 up = 1 else: up = down = 1 result = max(result, up, down) return result

7. 等差数列划分

7.1 问题描述

给定一个整数数组nums，返回数组中等差子数组的数目。

等差子数组是指至少有三个元素的连续子数组，且相邻元素之间的差值相等。

例如： 输入：nums = [1,2,3,4] 输出：3 解释：有3个等差子数组：[1,2,3]、[2,3,4]和[1,2,3,4]（自身）。

7.2 解题思路

定义dp[i]为以nums[i]结尾的等差子数组的个数。如果nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，那么： dp[i] = dp[i-1] + 1

这是因为新增的nums[i]可以与所有以nums[i-1]结尾的等差子数组组成新的等差子数组，再加上nums[i-2],nums[i-1],nums[i]这个新的三元组。

7.3 实现代码

def numberOfArithmeticSlices(nums): if len(nums) < 3: return 0 dp = [0] * len(nums) total = 0 for i in range(2, len(nums)): if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]: dp[i] = dp[i-1] + 1 total += dp[i] return total

8. 单词拆分

8.1 问题描述

给定一个非空字符串s和一个包含非空单词列表的字典wordDict，判定s是否可以被空格拆分为一个或多个在字典中出现的单词。

例如： 输入：s = "leetcode", wordDict = ["leet", "code"] 输出：true 解释："leetcode"可以拆分为"leet code"。

8.2 解题思路

定义dp[i]表示s的前i个字符能否被拆分。状态转移方程为： dp[i] = dp[j] && s[j:i] in wordDict，其中0 <= j < i

即，如果存在一个j，使得前j个字符可以拆分，且s[j:i]在字典中，那么前i个字符就可以拆分。

8.3 实现代码

def wordBreak(s, wordDict): word_set = set(wordDict) dp = [False] * (len(s)+1) dp[0] = True for i in range(1, len(s)+1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[-1]

9. 环形字符串中唯一的子字符串

9.1 问题描述

给定一个环形字符串s，返回s中唯一子字符串的数目。子字符串是字符串中连续的字符序列。

例如： 输入：s = "abc" 输出：7 解释：唯一的子字符串有："a","b","c","ab","bc","ca","abc"

9.2 解题思路

对于环形字符串，我们可以将其视为s+s，然后只考虑长度不超过len(s)的子字符串。为了避免重复，可以使用集合来存储所有子字符串。

9.3 实现代码

def countUniqueSubstrings(s): n = len(s) extended = s + s unique = set() for i in range(n): for j in range(i+1, i+n+1): if j - i <= n: unique.add(extended[i:j]) return len(unique)

10. 动态规划解题技巧总结

1. 状态定义是关键：大多数子数组问题都可以定义为"以第i个元素结尾的子数组的某种属性"。

2. 空间优化技巧：当状态转移只依赖前一个或前几个状态时，可以用变量代替数组。

3. 边界条件处理：特别注意数组为空、全正、全负等特殊情况。

4. 多状态维护：对于乘积等问题，可能需要同时维护最大和最小两个状态。

5. 环形数组处理：通常可以转化为普通数组问题处理，或者考虑两种不同情况。

在实际面试中，建议先明确状态定义，写出状态转移方程，然后考虑边界条件和空间优化。动态规划问题往往代码简洁，但思路需要非常清晰。