如何用动态规划解决数组分割最小化子数组最大值之和问题？

问题概述 #

给定长度为N的整数数组a_n，需将其分割为若干连续子数组，满足：

1. 每个子数组的和不超过给定整数M；
2. 找到一种分割方式，使各子数组的最大值之和最小。

若不存在合法分割（比如数组中存在元素大于M），返回-1。

示例 #

输入: n = 8, m = 17, arr = [2, 2, 2, 8, 1, 8, 2, 1]
输出: 12
解释: 最优分割为 [2, 2, 2], [8, 1, 8], [2, 1]，各子数组最大值之和为 2 + 8 + 2 = 12

约束 #

• 0 ≤ N ≤ 100000
• 数组元素取值范围：0 ≤ a_i ≤ 1000000

你的解法问题所在 #

你用的贪心策略（每次尽可能把更多元素塞进当前子数组）是局部最优，但无法保证全局最优。比如示例中你的代码分割出[2,2,2,8,1]和[8,2,1]，最大值之和为8+8=16，远大于最优解。

原因很简单：为了装更多元素，你被迫把大元素（比如第一个8）和前面的小元素放在一起，导致后面的8又不得不单独成为子数组的最大值，两次累加后总和变大。这种情况下，必须用动态规划来考虑全局最优选择。

正确解法：动态规划 #

核心思路 #

1. 特殊情况先处理：

   • 数组为空时返回0；
   • 如果数组中有元素大于M，直接返回-1（单个元素都无法满足和的限制，不可能分割）。

2. DP定义：
   设dp[i]表示前i个元素（即数组的a[0..i-1]部分）分割后的最小最大值之和。

3. 初始条件：
   dp[0] = 0（没有元素时总和为0），其余dp[i]初始化为无穷大（表示初始状态下无法达到该状态）。

4. 状态转移：
   对于每个i，我们需要找到所有合法的分割点j（0 ≤ j < i），使得子数组a[j..i-1]的和不超过M。此时dp[i]的取值为dp[j] + max(a[j..i-1])的最小值，也就是：

   dp[i] = min{ dp[j] + max(a[j..i-1]) | sum(a[j..i-1]) ≤ M }
   

实现方式 #

1. 暴力DP（适合小数据，理解核心逻辑）

这种方法时间复杂度为O(n²)，无法处理n=1e5的情况，但能帮你理解DP的核心：

import sys

def min_max_sum_bruteforce(arr, M):
    n = len(arr)
    if n == 0:
        return 0
    # 检查是否有元素超过M
    for num in arr:
        if num > M:
            return -1
    # 前缀和数组，快速计算区间和
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + arr[i]
    
    dp = [sys.maxsize] * (n + 1)
    dp[0] = 0
    
    for i in range(1, n+1):
        # 找到最小的j，使得sum(a[j..i-1]) <= M
        left = 0
        while prefix_sum[i] - prefix_sum[left] > M:
            left += 1
        # 从i-1往left遍历，维护当前区间的最大值
        current_max = 0
        for j in range(i-1, left-1, -1):
            current_max = max(current_max, arr[j])
            if dp[j] + current_max < dp[i]:
                dp[i] = dp[j] + current_max
    return dp[n] if dp[n] != sys.maxsize else -1

# 测试示例
print(min_max_sum_bruteforce([2,2,2,8,1,8,2,1], 17))  # 输出12

2. 优化DP（处理大数据，O(n logn)时间）

对于n=1e5的情况，暴力DP会超时，我们需要用单调队列维护区间最大值+线段树维护区间dp最小值来优化：

import sys
from collections import deque

def min_max_sum_optimized(arr, M):
    n = len(arr)
    if n == 0:
        return 0
    # 检查是否有元素超过M
    for num in arr:
        if num > M:
            return -1
    # 前缀和数组
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + arr[i]
    
    dp = [sys.maxsize] * (n + 1)
    dp[0] = 0

    # 线段树：维护区间内dp[j]的最小值
    class SegmentTree:
        def __init__(self, size):
            self.n = 1
            while self.n < size:
                self.n <<= 1
            self.min_tree = [sys.maxsize] * (2 * self.n)
        
        def update(self, pos, value):
            pos += self.n
            if self.min_tree[pos] > value:
                self.min_tree[pos] = value
                pos >>= 1
                while pos >= 1:
                    new_val = min(self.min_tree[2*pos], self.min_tree[2*pos+1])
                    if self.min_tree[pos] == new_val:
                        break
                    self.min_tree[pos] = new_val
                    pos >>= 1
        
        def query_min(self, l, r):
            res = sys.maxsize
            l += self.n
            r += self.n
            while l <= r:
                if l % 2 == 1:
                    res = min(res, self.min_tree[l])
                    l += 1
                if r % 2 == 0:
                    res = min(res, self.min_tree[r])
                    r -= 1
                l >>= 1
                r >>= 1
            return res
    
    st = SegmentTree(n + 1)
    st.update(0, 0)
    # 单调队列：存储数组索引，对应arr值递减，维护区间最大值的候选位置
    q = deque()

    for i in range(1, n+1):
        current_num = arr[i-1]
        # 维护单调队列，移除所有值<=current_num的元素（它们不可能成为后续区间的最大值）
        while q and arr[q[-1]] <= current_num:
            q.pop()
        q.append(i-1)

        # 二分查找找到最小的left，使得sum(a[left..i-1]) <= M
        left = 0
        low, high = 0, i-1
        while low <= high:
            mid = (low + high) // 2
            if prefix_sum[i] - prefix_sum[mid] <= M:
                left = mid
                high = mid - 1
            else:
                low = mid + 1
        
        # 移除队列中小于left的元素（这些位置对应的区间和会超过M）
        while q and q[0] < left:
            q.popleft()
        
        # 遍历队列中的最大值候选，计算每个区间的最小dp[j]+max_val
        min_total = sys.maxsize
        prev = left - 1
        for p in q:
            if p > i-1:
                break
            # 查询区间[prev+1, p]内的最小dp[j]
            current_min_dp = st.query_min(prev+1, p)
            min_total = min(min_total, current_min_dp + arr[p])
            prev = p
        
        dp[i] = min_total
        st.update(i, dp[i])
    
    return dp[n] if dp[n] != sys.maxsize else -1

# 测试示例
print(min_max_sum_optimized([2,2,2,8,1,8,2,1], 17))  # 输出12

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