本文介绍一种基于动态规划与滑动窗口优化的高效算法，用于将整数数组按长度约束划分为连续子数组，使得所有子数组（最大值−最小值）之和达到最大。时间复杂度为 o((b−a+1)·n)，显著优于暴力回溯。
本文介绍一种基于动态规划与滑动窗口优化的高效算法，用于将整数数组按长度约束划分为连续子数组，使得所有子数组（最大值−最小值）之和达到最大。时间复杂度为 o((b−a+1)·n)，显著优于暴力回溯。
在解决“将数组划分为长度介于 a 到 b 之间的连续子数组，使各子数组极差（max − min）之和最大”这一问题时，朴素的回溯或 BFS 方法（如原始代码中使用的队列枚举）时间复杂度高达指数级，无法应对中等规模输入（例如 n > 30）。幸运的是，该问题具备最优子结构和重叠子问题特性，天然适配动态规划（DP），并可通过单调双端队列优化区间极值计算，实现线性单次扫描。
核心思路：DP 状态 + 滑动窗口预处理
我们定义 DP 状态 best_weight[i] 表示处理完前 i 个元素（即 numbers[0:i]）所能获得的最大极差总和；对应地，prev_index[i] 记录达成该最优值时，上一个子数组的起始下标（便于最终重构划分方案）。
关键挑战在于：对每个可能的结束位置 j，需快速计算所有满足 j−b+1 ≤ i ≤ j−a+1 的起始位置 i 对应的子数组 numbers[i:j+1] 的极差。若对每个子数组都调用 max()/min()，单次耗时 O(b−a)，整体退化为 O(n·(b−a)²)。
✅ 解决方案：复用滑动窗口极值算法。我们不逐个枚举长度，而是对每个固定长度 L = a 启动一次单调双端队列扫描，同时在扩展过程中动态维护当前窗口 [i, j]（j−i+1 ∈ [a, b]）的 min/max，并即时更新 DP 状态。
以下为完整实现（含注释）：
from collections import deque
def window_mins_maxes(size, array):
"""O(n) 单次扫描，返回所有长度为 size 的窗口的 (end_idx, min_val, max_val)"""
if size == 0 or not array:
return
min_vals, min_pos = deque(), deque()
max_vals, max_pos = deque(), deque()
for i, val in enumerate(array):
# 移除过期索引（窗口左边界超出）
if 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, min_vals[0], max_vals[0])
def partition_array(numbers, min_len, max_len):
n = len(numbers)
if max_len < min_len or n < min_len:
return (None, None)
# best_weight[i] = 前 i 个元素的最大极差和；索引 0..n，额外预留 best_weight[n] 表示全数组处理完毕
best_weight = [None] * (n + 1)
prev_index = [None] * (n + 1)
best_weight[0] = 0 # 空前缀和为 0
# 主循环：对每个以 i 结尾、长度为 min_len 的窗口，向后延伸至 max_len
for end, win_min, win_max in window_mins_maxes(min_len, numbers):
start = end - min_len + 1
base_weight = best_weight[start] # 上一状态：numbers[0:start] 的最优解
if base_weight is None:
continue
# 从长度 min_len 开始，逐步扩展子数组至长度 max_len
curr_min, curr_max = win_min, win_max
# 当前窗口 [start, end] 已确定，尝试向右扩展：end+1, end+2, ..., 最多到 start + max_len - 1
for j in range(end + 1, min(start + max_len, n + 1)):
# 更新 [start, j-1] 的极差（j 是新结束索引，对应子数组 numbers[start:j]）
if j - 1 < n: # j-1 是实际最后一个元素下标
if numbers[j - 1] < curr_min:
curr_min = numbers[j - 1]
if numbers[j - 1] > curr_max:
curr_max = numbers[j - 1]
diff = curr_max - curr_min
new_weight = base_weight + diff
# 更新 DP 状态：若更优，则记录
if best_weight[j] is None or best_weight[j] < new_weight:
best_weight[j] = new_weight
prev_index[j] = start
# 检查是否能覆盖整个数组
if best_weight[n] is None:
return (None, None)
# 回溯构造划分方案
path = [n]
while prev_index[path[-1]] is not None:
path.append(prev_index[path[-1]])
path = list(reversed(path))
partitioned = [numbers[path[i]:path[i + 1]] for i in range(len(path) - 1)]
return (best_weight[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) —— 无法划分注意事项与优化要点
- 时间复杂度：主循环调用 window_mins_maxes(min_len, ...) 为 O(n)，内部扩展最多 (max_len − min_len) 步，故总时间为 O(n·(max_len − min_len + 1))，远优于暴力的 O(b^ⁿ)。
- 空间复杂度：仅需 O(n) 存储 DP 数组及双端队列（队列长度 ≤ max_len），符合线性要求。
- 边界鲁棒性：代码显式处理了 min_len > max_len、数组过短、无法完全划分等异常情况，返回 (None, None) 明确标识失败。
- 重构路径：利用 prev_index 数组反向追踪，可在 O(k) 时间内（k 为子数组数量）还原具体划分，无需额外存储中间状态。
- 不可贪心：该问题不能使用贪心策略（如每次取最长/极差最大子数组），因局部最优不保证全局最优。DP 是理论最优且实践高效的解法。
综上，该方案将经典 DP 框架与滑动窗口技巧深度融合，在保证正确性的同时实现了接近理论下限的运行效率，是处理此类带约束区间划分优化问题的标准范式。
