本文介绍一种时间复杂度为 o((b−a+1)·n) 的动态规划解法，用于将整数数组划分为长度在 [a,b] 区间内的连续子数组，使得各子数组（max−min）之和最大，并支持重构最优划分方案。
本文介绍一种时间复杂度为 o((b−a+1)·n) 的动态规划解法，用于将整数数组划分为长度在 [a,b] 区间内的连续子数组，使得各子数组（max−min）之和最大，并支持重构最优划分方案。
该问题本质是带约束的序列划分优化问题：给定整数数组 nums 和子数组长度上下界 a（最小）、b（最大），需将其按原始顺序划分为若干连续子数组，每个子数组长度 ∈ [a, b]，目标是最大化所有子数组的 (max − min) 之和。
暴力枚举所有合法划分方式的时间复杂度为指数级，而本解法通过动态规划 + 单调队列优化的滑动窗口极值预处理，将时间复杂度降至线性级别（相对于输入规模与窗口宽度之积）。
核心思路
状态定义：设 dp[i] 表示处理完前 i 个元素（即 nums[0:i]）时所能获得的最大极差和。特别地，dp[0] = 0（空数组贡献为 0），最终答案为 dp[n]（n = len(nums)）。
状态转移：对每个位置 j（作为某子数组的右端点），枚举其左端点 i，要求子数组 nums[i:j] 长度满足 a ≤ j−i ≤ b。则： $$ dp[j] = \max_{i \in [j-b,\; j-a]} \left{ dp[i] + \left(\max(nums[i:j]) - \min(nums[i:j])\right) \right} $$
关键优化：滑动窗口极值复用
直接对每个 [i,j] 计算 max/min 将导致 O(n²) 时间。我们改用单调双端队列，在遍历过程中维护固定左端点 i 下、右端点 j 递增时的窗口 [i, j] 的实时 min 和 max。更进一步，我们按子数组长度 a 为基准启动窗口，然后向右扩展至最多 b−a 步，同步更新极值并计算 dp[j]。
实现细节与代码
以下为完整 Python 实现（含注释与边界处理）：
from collections import deque
def window_mins_maxes(size, array):
"""生成所有长度为 size 的滑动窗口的 (end_index, min_val, max_val)"""
if size > len(array):
return
min_vals, min_pos = deque(), deque()
max_vals, max_pos = deque(), deque()
for i, val in enumerate(array):
# 移除过期索引（窗口左边界为 i-size+1，故索引 <= i-size 过期）
if min_pos and min_pos[0] <= i - size:
min_vals.popleft()
min_pos.popleft()
if max_pos and max_pos[0] <= i - size:
max_vals.popleft()
max_pos.popleft()
# 维护 min_vals 单调递增（队首最小）
while min_vals and val <= min_vals[-1]:
min_vals.pop()
min_pos.pop()
min_vals.append(val)
min_pos.append(i)
# 维护 max_vals 单调递减（队首最大）
while max_vals and max_vals[-1] <= val:
max_vals.pop()
max_pos.pop()
max_vals.append(val)
max_pos.append(i)
# 当窗口填满 size 个元素时输出
if i >= size - 1:
yield (i + 1, min_vals[0], max_vals[0])
def partition_array(nums, a, b):
n = len(nums)
if b < a or n < a:
return (None, None)
# dp[i] = 前 i 个元素的最大极差和；prev[i] = 最优划分中第 i 位前一个分割点
dp = [None] * (n + 1) # dp[0..n]，dp[n] 为最终答案
prev = [None] * (n + 1)
dp[0] = 0
# 对每个以长度 a 启动的窗口 [i, j)，j = i+a
for j, min_val, max_val in window_mins_maxes(a, nums):
i = j - a # 当前窗口左端点
if dp[i] is None:
continue # 前缀不可达，跳过
# 尝试扩展窗口：从长度 a 到 b，即右端点从 j 到 j+(b-a)
cur_min, cur_max = min_val, max_val
# 先处理长度 a 的情况（即 j 本身）
new_score = dp[i] + (cur_max - cur_min)
if dp[j] is None or dp[j] < new_score:
dp[j] = new_score
prev[j] = i
# 扩展右端点 k 从 j+1 到 min(j+b-a, n)
k = j
while k < min(j + b - a, n):
k += 1
# 更新当前窗口 [i, k) 的极值
if nums[k-1] < cur_min:
cur_min = nums[k-1]
if nums[k-1] > cur_max:
cur_max = nums[k-1]
new_score = dp[i] + (cur_max - cur_min)
if dp[k] is None or dp[k] < new_score:
dp[k] = new_score
prev[k] = i
if dp[n] is None:
return (None, None)
# 重构划分路径
path = [n]
while prev[path[-1]] is not None:
path.append(prev[path[-1]])
path = path[::-1] # 反转得到升序分割点
partitioned = [nums[path[i]:path[i+1]] for i in range(len(path)-1)]
return (dp[n], partitioned)
# 测试用例
print(partition_array([5, 8, 4, 5, 1, 3, 5, 1, 3, 1], 3, 7))
# 输出: (12, [[5, 8, 4], [5, 1, 3], [5, 1, 3, 1]])
print(partition_array([1, 6, 2, 2, 5, 2, 8, 1, 5, 6], 3, 4))
# 输出: (16, [[1, 6, 2], [2, 5, 2, 8], [1, 5, 6]])
print(partition_array([5, 8, 4, 5, 1, 3, 5, 1, 3, 1, 2], 4, 5))
# 输出: (None, None) —— 无法划分注意事项与总结
- 时间复杂度：O((b − a + 1) × n)。外层 window_mins_maxes(a, nums) 耗时 O(n)，内层对每个起始窗口最多扩展 b−a 次，每次 O(1) 更新极值。
- 空间复杂度：O(n)，主要消耗于 dp 和 prev 数组及双端队列（队列长度 ≤ a）。
- 边界鲁棒性：函数自动处理 a > b、len(nums) < a 或无解情形，返回 (None, None)。
- 重构能力：不仅返回最大极差和，还通过 prev 数组回溯出具体子数组划分，满足实际应用需求。
- 适用场景：适用于中等规模数据（如 n ≤ 10⁵, b−a ≤ 100），远优于指数级暴力搜索。
该方案融合了经典 DP 思想与单调队列技巧，是解决带长度约束的序列划分优化问题的典型范式。
