求高效算法：将整数数组划分子数组以最大化差值和

问题回顾 #

给定一个未排序整数数组，要把它拆成若干长度在a到b之间的子数组（元素顺序不能乱），让所有子数组的「最大值减最小值」的总和最大。要是没法拆（比如总长度凑不出符合要求的段数），就返回无法完成。

现有解法的问题 #

你当前用的BFS枚举所有划分组合属于暴力搜索，时间复杂度是指数级的——数组长度稍微大一点（比如超过20），程序就会直接卡住，完全没法用。

高效解法：动态规划+单调队列优化 #

核心想法 #

用动态规划记录到每个位置的最大差值和，再用单调队列快速算出滑动窗口的最大/最小值，避免重复计算，把时间复杂度降到线性级别附近。

1. DP定义：设dp[i]表示前i个元素划分后的最大差值和，目标就是求dp[n]（n是数组总长度）。
2. 状态转移：想算出dp[i]，就得看所有能转移到i的位置j——j要满足i-b ≤ j ≤ i-a（这样j+1到i的长度就在a到b之间）。此时dp[i] = max(dp[j] + (max(j+1到i的元素) - min(j+1到i的元素)))。
3. 关键优化：直接算每个区间的max/min会重复计算，用单调队列可以在O(1)时间维护滑动窗口的max和min，把这部分开销降下来。

具体实现步骤 #

• 初始化dp[0] = 0（前0个元素没东西，差值和为0），其他dp[i]设为负无穷（表示暂时没法划分到这个位置）。
• 用两个单调队列：一个存索引，维护窗口内的最大值；另一个存索引，维护窗口内的最小值。
• 遍历每个位置i（从1到n）：
  • 维护最大值队列：把队尾所有比当前元素小的索引删掉（它们不可能成为后续窗口的最大值），再把当前元素的索引加进去；同时删掉队列里超出窗口左边界（i-b）的索引。
  • 维护最小值队列：类似地，删掉队尾所有比当前元素大的索引，加入当前索引；再删掉超出左边界的索引。
  • 找合法的j范围：j从max(0, i-b)到i-a，如果这个范围有效（end_j >= start_j），就遍历每个j，用队列里的max和min计算差值，更新dp[i]的最大值。
• 最后看dp[n]：如果还是负无穷，说明没法划分；否则就是最大差值和。

代码实现 #

def max_partition_diff_sum(nums, a, b):
    n = len(nums)
    dp = [-float('inf')] * (n + 1)
    dp[0] = 0  # 前0个元素的差值和为0

    # 单调队列：存储元素索引，分别维护窗口的最大值和最小值
    max_deque = []
    min_deque = []

    for i in range(1, n + 1):
        current_num = nums[i-1]
        # 维护最大值队列：移除队尾比当前数小的元素，保证队列单调递减
        while max_deque and nums[max_deque[-1]] <= current_num:
            max_deque.pop()
        max_deque.append(i-1)
        # 移除超出窗口左边界的元素（窗口左边界是i-b，因为j >= i-b → j+1 >= i-b+1）
        while max_deque[0] < i - b:
            max_deque.pop(0)
        
        # 维护最小值队列：移除队尾比当前数大的元素，保证队列单调递增
        while min_deque and nums[min_deque[-1]] >= current_num:
            min_deque.pop()
        min_deque.append(i-1)
        while min_deque[0] < i - b:
            min_deque.pop(0)
        
        # 遍历所有合法的j，更新dp[i]
        start_j = max(0, i - b)
        end_j = i - a
        if end_j >= start_j:
            for j in range(start_j, end_j + 1):
                if dp[j] == -float('inf'):
                    continue
                current_max = nums[max_deque[0]]
                current_min = nums[min_deque[0]]
                dp[i] = max(dp[i], dp[j] + (current_max - current_min))
    
    return dp[n] if dp[n] != -float('inf') else "无法完成划分"

# 测试示例
print(max_partition_diff_sum([5, 8, 4, 5, 1, 3, 5, 1, 3, 1], 3, 7))  # 输出12
print(max_partition_diff_sum([1, 6, 2, 2, 5, 2, 8, 1, 5, 6], 3, 4))  # 输出16
print(max_partition_diff_sum([5, 8, 4, 5, 1, 3, 5, 1, 3, 1, 2], 4, 5))  # 输出无法完成划分

复杂度对比 #

• 原来的暴力解法：指数级时间，n=20就基本跑不动。
• 现在的解法：时间复杂度是O(n*(b-a+1))，如果b和a的差距不大（比如题目里的情况），近似O(n)，n到1e5都能轻松处理。空间复杂度是O(n)，主要是DP数组和单调队列的开销。

可选进阶优化 #

如果b和a的差距特别大（比如b是a的几百倍），还可以用单调队列维护dp[j] - max(j+1到i)和dp[j] + min(j+1到i)这类组合值，把状态转移的时间降到O(1)，总时间复杂度直接到O(n)。不过一般场景下，上面的解法已经足够高效了。

内容的提问来源于stack exchange，提问作者Maxim