如何高效分割数组以最大化各子数组极差之和

先直接说结论：本文介绍一种基于动态规划与滑动窗口优化的高效算法，用于将整数数组按长度约束划分为连续子数组，使得所有子数组（最大值−最小值）之和达到最大。时间复杂度为 O((b−a+1)·n)，显著优于暴力回溯。

不知你有没有遇到过这样的问题：将一个数组切分成若干段，每段长度在 a 到 b 之间，要求所有段内最大值减最小值的总和最大。用暴力回溯？复杂度是指数级的，数组长度稍微上到 30 就趴下了。好消息是，这个问题天然具备最优子结构和重叠子问题——动态规划正好对口。再配合单调队列优化区间极值计算，就能做到线性扫描。

核心思路：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 dequedef 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(n) 的 DP 数组和双端队列，队列长度不超过 max_len，线性级别，很友好。
• 边界鲁棒性：代码把各种异常都考虑进去了——min_len > max_len、数组太短导致无法完整划分等，都会返回 (None, None) 明确告诉你“这活儿干不了”。
• 重构路径：回溯时利用 prev_index 反向追踪，O(k) 时间就能拿到具体分段（k 是子数组数量），不需要额外存储中间状态。
• 不可贪心：特别注意，这题不能用贪心策略。别想着每次挑极差最大的子数组就能凑出全局最优——局部最优≠全局最优。DP 才是理论上最优、实践上也高效的解法。

总的来说，这个方案把经典 DP 框架和滑动窗口的优化粘合在一起，既保证了正确性，又把运行效率压到了理论下限附近。对于这类带长度约束的区间划分优化问题，它算是一个标准范式了。