求数组分割为指定子数组的局部最大值最小和及算法优化

你的枚举所有分割方式的思路虽然直观，但时间复杂度确实是O(2ⁿ)，当数组长度较大时完全不可用。这里用动态规划可以大幅优化效率，时间复杂度降至O(n²k)，适用于更大规模的输入。

思路说明 #

定义dp[i][k]为：将数组前i个元素（即arr[0..i-1]）分割成k个子数组时，局部最大值的最小总和。

状态转移方程 #

要计算dp[i][k]，我们需要考虑所有可能的前一个分割点j（k-1 ≤ j < i）：

• 前j个元素分割成k-1个子数组的最小和是dp[j][k-1]
• 第k个子数组是arr[j..i-1]，其最大值为max(arr[j..i-1])
• 因此dp[i][k] = min(dp[j][k-1] + max(arr[j..i-1]))，遍历所有合法的j取最小值

边界条件 #

1. 当k=1时，dp[i][1]就是前i个元素的最大值，因为只能分成一个子数组
2. 当i=k时，每个子数组只能有一个元素，dp[i][k]就是前i个元素的和（每个元素都是自己子数组的最大值）

JavaScript实现代码 #

function minMaxSum(arr, k) {
    const n = arr.length;
    // 边界情况：分割数等于数组长度，每个元素单独成组
    if (k === n) {
        return arr.reduce((sum, num) => sum + num, 0);
    }
    // 初始化dp数组，dp[i][k]表示前i个元素分成k组的最小和
    const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
    
    // 处理k=1的情况：前i个元素分成1组，和为最大值
    let currentMax = 0;
    for (let i = 1; i <= n; i++) {
        currentMax = Math.max(currentMax, arr[i - 1]);
        dp[i][1] = currentMax;
    }
    
    // 填充dp数组，k从2到指定的分割数
    for (let groups = 2; groups <= k; groups++) {
        // 前i个元素分成groups组，i至少为groups（每个组至少一个元素）
        for (let i = groups; i <= n; i++) {
            // 遍历所有可能的前一个分割点j
            let subMax = 0;
            // 从i-1倒着往前找j，这样可以维护当前子数组的最大值，避免重复计算
            for (let j = i - 1; j >= groups - 1; j--) {
                subMax = Math.max(subMax, arr[j]);
                dp[i][groups] = Math.min(dp[i][groups], dp[j][groups - 1] + subMax);
            }
        }
    }
    
    return dp[n][k];
}

// 测试示例
console.log(minMaxSum([2, 3, 1, 4, 5, 6], 3)); // 输出10

复杂度分析 #

• 时间复杂度：O(n²k)，其中n是数组长度，k是分割的子数组数量。相对于枚举法的O(2ⁿ)，在n≥10时就已经有数量级的提升。
• 空间复杂度：O(nk)，用于存储dp数组，也可以通过优化空间将其降至O(n)（因为计算第k组时只需要第k-1组的数据）。

代码优化说明 #

在计算max(arr[j..i-1])时，我们采用倒序遍历j的方式，每次只需要和当前元素比较就能得到子数组的最大值，避免了每次都重新遍历子数组计算最大值，节省了O(n)的时间开销。

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