本文介绍一种基于动态规划与滑动窗口优化的高效算法，用于将整数数组按长度约束划分为连续子数组，使得所有子数组（最大值−最小值）之和达到最大。时间复杂度为 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] = size - 1:
yield (i, min_vals[0], max_vals[0])
def partition_array(numbers, min_len, max_len):
n = len(numbers)
if max_len 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] <h3>注意事项与优化要点</h3>
- 时间复杂度：主循环调用 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 框架与滑动窗口技巧深度融合，在保证正确性的同时实现了接近理论下限的运行效率，是处理此类带约束区间划分优化问题的标准范式。
