410-分割数组的最大值(Split Array Largest Sum)

原文链接: https://leetcode-cn.com/problems/split-array-largest-sum

英文原文

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= m <= min(50, nums.length)

中文题目

给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。

设计一个算法使得这 m 个子数组各自和的最大值最小。

示例 1：

输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

示例 2：

输入：nums = [1,2,3,4,5], m = 2
输出：9

示例 3：

输入：nums = [1,4,4], m = 3
输出：4

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 10⁶
1 <= m <= min(50, nums.length)

通过代码

高赞题解

写在前面的话：

动态规划的写法其实是穷举：按照长度、前缀，枚举最后一个划分，记录每一步结果。细节比较多，需要作图 + 仔细讨论边界情况，并且熟悉二维状态数组、三层 for 循环的写法；
本题的二分查找的思路来源于二分查找的基本思想（应用）：查找一个有范围的整数，关键在于利用单调性逼近这个整数。「力扣」上很多问题都基于本题设计，属于「使用二分查找最大值最小化」的一类问题的例题。

题意分析：各自和的最大值最小，这句话读起来有一点点绕。我们拆分一下：

由于数组是确定的，其中一组分得多，相应地另一组分到的值就少。所以对于任意一种拆分（切成 m 段），这 m 段可以取最大值 val；
我们需要找到一种拆分，使得这个最大值 val 的值是所有分成 m 段拆分里值最小的那个；具体怎么拆，题目不用我们求，只需要我们计算出 val 的值。

方法一：动态规划

枚举所有的分割的情况，例如题目中的输入数组 [7, 2, 5, 10, 8] 分割成 $2$ 个非空连续子数组，可以有以下 $4$ 种方式：

[7, | 2, 5, 10, 8]；
[7, 2, | 5, 10, 8]；
[7, 2, 5, | 10, 8]；
[7, 2, 5, 10, | 8]。

比较容易想到的递归结构是：

找到最后一个分割，求出这个分割的连续子数组的和，与之前的分割取最大值；
枚举最后一个分割，找出所有最大值中最小的那一个。

整个过程稍微有一些繁琐，但是思想是直接的：对于所有长度的 前缀区间（题目中的关键信息是子数组连续，所以考虑前缀区间），枚举所有可能的分割，并记录每一步的结果，递推完成计算。以题目中的示例 [7, 2, 5, 10, 8] 为例：

先考虑 所有前缀区间 分割成 $1$ 个非空连续子数组的情况：

[7] 分割成 $1$ 个非空连续子数组的和，就是整个数组的和 $7$，下同；
[7, 2] 分割成 $1$ 个非空连续子数组的和，就是整个数组的和 $9$；
[7, 2, 5] 分割成 $1$ 个非空连续子数组的和，就是整个数组的和 $14$；
[7, 2, 5, 10] 分割成 $1$ 个非空连续子数组的和，就是整个数组的和 $24$；
[7, 2, 5, 10, 8] 分割成 $1$ 个非空连续子数组的和，就是整个数组的和 $32$；

再考虑 所有前缀区间 分割成 $2$ 个非空连续子数组的情况：

[7] 不能分割成 $2$ 个非空连续子数组的和；
[7, 2] 分割成 $2$ 个非空连续子数组，只有 $1$ 种分割情况：[7, | 2] ，其中「[7] 分割成 $1$ 个非空连续子数组」的情况我们在第 1 步计算过；
[7, 2, 8] 分割成 $2$ 个非空连续子数组，有 $2$ 种分割情况：
- [7, | 2, 8] ，其中「[7] 分割成 $1$ 个非空连续子数组」的情况我们在第 1 步计算过；
- [7, 2, | 8] ，其中「[7, 2] 分割成 $1$ 个非空连续子数组」的情况我们在第 2 步计算过；

分析到这里，可以把递推结构形式化描述成如下：

第 1 步：定义状态

dp[i][k] 表示：将前缀区间 [0, i] 被分成 k 段的各自和的最大值的最小值记为 dp[i][k]，那么前缀区间 [0, j] （这里 j < i）被分成 k - 1 段各自和的最大值的最小值为 dp[j][k - 1]。

即：第一维是第 k 个分割的最后一个元素的下标 i ，第二维是分割的总数 i。

第 2 步：推导状态转移方程

$$
dp[i][k] = \max(dp[j][k - 1], ; rangeSum(j + 1,i))
$$

这里 $rangeSum(j + 1, i)$ 表示数组 nums[j + 1..i] 的区间和，它可以先计算出所有前缀和，然后以 $O(1)$ 的方式计算出区间和。

上面的状态转移方程中，j 的值需要枚举。我们画图分析：

由于区间 [0, j] 一定要分成 k - 1 个非空连续子数组；
j 的意义是：第 k - 1 个分割的最后一个元素的下标；
而下标 k - 1 的前面（不包括 k - 1），一共有 k - 1 个元素（这一条只要是下标从 0 开始均成立）；
故 j 的枚举从 k - 2 开始，到 i - 1 结束，因为第 k 个分割至少要有 $1$ 个元素。

第 3 步：思考初始化

由于要找最小值，初值赋值成为一个不可能达到的很大的值；
分割数为 1 ，即不分割的情况，所有的前缀和就是依次的状态值。

第 4 步：思考输出

dp[len][k]，根据状态定义，这是显然的。

下面给出题目中的示例 [7, 2, 5, 10, 8] 的状态计算表，为了更突出一般性，把 m 设置成为数组的长度 $5$：

编码的思考路径：

我们按照阶段、状态和选择进行分析，依次把三层循环写下来：

阶段：依次计算长度为 $1$ 的区间、长度为 $2$ 的区间，直到题目要求的长度为 $m$ 的区间；
状态：前缀区间 [0, i] 的状态值，由于 i 要被分成 k 份，前缀区间里至少要有 k 个元素，最小前缀区间 k 个元素的最后一个元素的下标为 k - 1，故 i 从 k - 1 开始到 len - 1；
选择：枚举第 k - 1 个分割的最后一个元素的下标，根据上面的分析，从 k - 2 到 i - 1。

参考代码：

[]
import java.util.Arrays;

public class Solution {

    public int splitArray(int[] nums, int m) {
        int len = nums.length;
        // 前缀和，preSum[i] = sum[0..i)
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 区间 [i..j] 的和 preSum(j + 1) - preSum(i)
        int[][] dp = new int[len][m + 1];
        // 初始化：由于要找最小值，初值赋值成为一个不可能达到的很大的值
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        // 分割数为 1 ，即不分割的情况，所有的前缀和就是依次的状态值
        for (int i = 0; i < len; i++) {
            dp[i][1] = preSum[i + 1];
        }

        // 从分割数为 2 开始递推
        for (int k = 2; k <= m; k++) {
            // 还未计算出的 i 是从 j 的最小值的下一位开始，因此是 k - 1
            for (int i = k - 1; i < len; i++) {
                // j 表示第 k - 1 个区间的最后一个元素额下标，最小值为 k - 2，最大值为 len - 2（最后一个区间至少有 1 个元素）
                for (int j = k - 2; j < i; j++) {
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], preSum[i + 1] - preSum[j + 1]));
                }
            }
        }
        return dp[len - 1][m];
    }
}

复杂度分析：

时间复杂度：$O(N^2M)$，这里 $N$ 是输入数组的长度，M 是题目中给出的分割数，三层 for 循环递推；
空间复杂度：$O(N^2)$，状态数组的大小为。

方法二：二分查找

关键字分析：这个题目非常关键的字眼是：非负整数数组、非空和连续。尤其是「非负整数数组」和「连续」这两个信息，请读者看完下面分析以后再来体会「连续」为什么那么重要。

解题思路的直觉来源：基于「力扣」第 69 题、第 287 题，知道二分查找的应用：可以用于查找一个有范围的整数，就能想到是不是可以使用二分查找去解决这道问题。

事实上，二分查找最典型的应用我们都见过，《幸运 52》猜价格游戏，主持人说「低了」，我们就应该往高了猜。

这种二分查找的应用大家普遍的叫法是「二分答案」，即「对答案二分」。它是相对于二分查找的最原始形式「在一个有序数组里查找一个数」而言的。

挖掘单调性：使用二分查找的一个前提是「数组具有单调性」，我们就去想想有没有单调性可以挖掘，不难发现：

如果设置「数组各自和的最大值」很大，那么必然导致分割数很小；
如果设置「数组各自和的最大值」很小，那么必然导致分割数很大。

仔细想想，这里「数组各自和的最大值」就决定了一种分割的方法。再联系一下我们刚刚向大家强调的题目的要求连续和题目中给出的输入数组的特点: 非负整数数组。

那么，我们就可以通过调整「数组各自和的最大值」来达到：使得分割数恰好为 m 的效果。这里要注意一个问题：

注意事项：如果某个 数组各自和的最大值 恰恰好使得分割数为 m ，此时不能放弃搜索，因为我们要使得这个最大值 最小化，此时还应该继续尝试缩小这个 数组各自和的最大值 ，使得分割数超过 m ，超过 m 的最后一个使得分割数为 m 的 数组各自和的最大值 就是我们要找的 最小值。

这里想不太明白的话，可以举一个具体的例子：

例如：（题目中给出的示例）输入数组为 [7, 2, 5, 10, 8] ，m = 2 。如果设置 数组各自和的最大值 为 21，那么分割是 [7, 2, 5, | 10, 8]，此时 m = 2，此时，这个值太大，尝试一点一点缩小：

设置 数组各自和的最大值 为 20，此时分割依然是 [7, 2, 5, | 10, 8]，m = 2；
设置 数组各自和的最大值 为 19，此时分割依然是 [7, 2, 5, | 10, 8]，m = 2；
设置 数组各自和的最大值 为 18，此时分割依然是 [7, 2, 5, | 10, 8]，m = 2；
设置 数组各自和的最大值 为 17，此时分割就变成了 [7, 2, 5, | 10, | 8]，这时 m = 3。

m 变成 3 之前的值 数组各自和的最大值 18 是这个问题的最小值，所以输出 18。

参考代码：

[]
public class Solution {

    public int splitArray(int[] nums, int m) {
        int max = 0;
        int sum = 0;

        // 计算「子数组各自的和的最大值」的上下界
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }

        // 使用「二分查找」确定一个恰当的「子数组各自的和的最大值」，
        // 使得它对应的「子数组的分割数」恰好等于 m
        int left = max;
        int right = sum;
        while (left < right) {
            int mid = left + (right - left) / 2;

            int splits = split(nums, mid);
            if (splits > m) {
                // 如果分割数太多，说明「子数组各自的和的最大值」太小，此时需要将「子数组各自的和的最大值」调大
                // 下一轮搜索的区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是上一轮的反面区间 [left, mid]
                right = mid;
            }
        }
        return left;
    }

    /***
     *
     * @param nums 原始数组
     * @param maxIntervalSum 子数组各自的和的最大值
     * @return 满足不超过「子数组各自的和的最大值」的分割数
     */
    private int split(int[] nums, int maxIntervalSum) {
        // 至少是一个分割
        int splits = 1;
        // 当前区间的和
        int curIntervalSum = 0;
        for (int num : nums) {
            // 尝试加上当前遍历的这个数，如果加上去超过了「子数组各自的和的最大值」，就不加这个数，另起炉灶
            if (curIntervalSum + num > maxIntervalSum) {
                curIntervalSum = 0;
                splits++;
            }
            curIntervalSum += num;
        }
        return splits;
    }
}

说明：

以上代码实现中采用 while (left < right) 的写法表示退出循环以后 left == right 成立，这种通过「左右边界」向中间逼近，最后得到一个数的二分查找思考路径，我在「力扣」的题解区已经多次向大家介绍，并且强调了使用细节和注意事项，这里就不赘述了；
if (splits > m) 的反面是 splits <= m 此时，下一轮搜索区间是 [left, mid] ，这个时候我们没有排除掉 mid 这个值，符合我们上面的逻辑：当分割数恰好等于 m 的时候，尝试缩小 数组各自和的最大值。

复杂度分析：

时间复杂度：$O(N \log \sum nums)$，这里 $N$ 表示输入数组的长度，$\sum nums$ 表示输入数组的和，代码在 $[\max(nums), \sum nums]$ 区间里使用二分查找找到目标元素，而每一次判断分支需要遍历一遍数组，时间复杂度为 $O(N)$；
空间复杂度：$O(1)$ ，只使用到常数个临时变量。

练习

这些问题都如出一辙，请大家特别留意题目中出现的关键字「非负整数」、分割「连续」，思考清楚设计算法的关键步骤和原因，相信以后遇到类似的问题就能轻松应对。

「力扣」第 875 题：爱吃香蕉的珂珂（中等）
LCP 12. 小张刷题计划（中等）
「力扣」第 1482 题：制作 m 束花所需的最少天数（中等）
「力扣」第 1011 题：在 D 天内送达包裹的能力（中等）
「力扣」第 1552 题：两球之间的磁力（中等）

总结

这道题让我们「查找一个有范围的整数」，以后遇到类似问题，要想到可以尝试使用「二分」；
遇到类似使「最大值」最小化，这样的题目描述，可以好好跟自己做过的这些问题进行比较，看看能不能找到关联；
在代码层面上，这些问题的特点都是：在二分查找的判别函数里，需要遍历数组一次。

（本题解于 2020 年 11 月 14 日重写。）

统计信息

通过次数	提交次数	AC比率
41439	72988	56.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途