本文介绍一种时间复杂度为 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，故索引 = size - 1:
yield (i + 1, min_vals[0], max_vals[0])
def partition_array(nums, a, b):
n = len(nums)
if b cur_max:
cur_max = nums[k-1]
new_score = dp[i] + (cur_max - cur_min)
if dp[k] is None or dp[k] <h3>注意事项与总结</h3>
- 时间复杂度：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)
- 重构能力：不仅返回最大极差和，还通过 prev 数组回溯出具体子数组划分，满足实际应用需求。
- 适用场景：适用于中等规模数据（如 n ≤ 10⁵, b−a ≤ 100），远优于指数级暴力搜索。
该方案融合了经典 DP 思想与单调队列技巧，是解决带长度约束的序列划分优化问题的典型范式。
