跳至主要內容

分割数组的最大值：二分答案与贪心验证的经典组合

老张2026/4/30大约 8 分钟

分割数组的最大值：二分答案与贪心验证的经典组合

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 18 分钟 | 难度：⭐⭐⭐⭐

开篇故事

LeetCode 410 是一道 Hard 题，但如果你已经掌握了二分答案的框架，它其实就是一道"中等偏上"的题目。

这道题最经典的地方在于，它有两种截然不同的解法：动态规划和二分答案。DP 解法的时间复杂度是 O(n²m)，二分答案的时间复杂度是 O(n log S)，后者更快，但更难想到。

我在某次面试中遇到这道题，当时没有想到二分答案，用 DP 写出来了，面试官给了及格分但没有给高分。后来面试官告诉我，他期待的是二分答案。那次经历让我意识到，对于"最小化最大值"或"最大化最小值"类型的题目，二分答案应该是第一个想到的思路，而不是最后一个。

一、题目解析

题目（LeetCode 410）： 给定一个非负整数数组 nums 和一个整数 m，将数组分成 m 个非空的连续子数组（不能打乱元素顺序）。设计一个算法使得这 m 个子数组各自和的最大值最小。

示例：

  • nums = [7,2,5,10,8]，m = 2，输出：18（分法：[7,2,5] 和 [10,8]，最大和为 18）
  • nums = [1,2,3,4,5]，m = 2，输出：9（分法：[1,2,3,4] 和 [5]，最大和为 9；或 [1,2,3] 和 [4,5]，最大和为 9）

关键约束：

  • 答案空间：[max(nums), sum(nums)]
    • 下界：max(nums)，因为至少有一个子数组包含最大元素
    • 上界：sum(nums)，当 m=1 时只有一个子数组
  • 验证函数：给定最大子数组和上限 mid，用贪心算法检验能否将数组分成不超过 m 组

二、解法一：动态规划 O(n²m)

思路分析

dp[i][j] 表示将前 i 个元素分成 j 组的最小最大子数组和。

状态转移：dp[i][j] = min over k { max(dp[k][j-1], sum(k+1..i)) }

需要预计算前缀和来快速求子数组和。

完整代码

public class Solution1 {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        // 前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        // dp[i][j]：将前 i 个元素分成 j 组的最小最大和
        long[][] dp = new long[n + 1][m + 1];
        for (long[] row : dp) Arrays.fill(row, Long.MAX_VALUE);
        dp[0][0] = 0;

        for (int j = 1; j <= m; j++) {
            for (int i = 1; i <= n; i++) {
                for (int k = j - 1; k < i; k++) {
                    if (dp[k][j - 1] == Long.MAX_VALUE) continue;
                    long maxSum = Math.max(dp[k][j - 1], prefix[i] - prefix[k]);
                    dp[i][j] = Math.min(dp[i][j], maxSum);
                }
            }
        }

        return (int) dp[n][m];
    }
}

复杂度分析

  • 时间复杂度：O(n²m)。三重循环。
  • 空间复杂度：O(nm)。DP 数组。

三、解法二：二分答案 + 贪心验证 O(n log S)

思路分析

在答案空间 [max(nums), sum(nums)] 上二分，对每个候选答案 mid（表示"最大子数组和不超过 mid"），用贪心验证能否将数组分成不超过 m 组：

贪心策略：从左到右扫描，每次尽量往当前组里加元素；如果加入当前元素会超过 mid，就开新的一组。统计所需组数，与 m 比较。

贪心正确性： 这个贪心之所以正确，是因为每组尽量多装，可以让后面的组有更多空间，不会导致整体组数增多。如果某个切分方案需要超过 m 组，任何其他贪心的切分都不可能更少。

完整代码

public class Solution2 {
    public int splitArray(int[] nums, int m) {
        long left = 0, right = 0;
        for (int n : nums) {
            left = Math.max(left, n);
            right += n;
        }

        while (left < right) {
            long mid = left + (right - left) / 2;
            if (canSplit(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return (int) left;
    }

    private boolean canSplit(int[] nums, long maxSum, int m) {
        int parts = 1;
        long currentSum = 0;
        for (int n : nums) {
            if (currentSum + n > maxSum) {
                parts++;
                currentSum = 0;
                if (parts > m) return false;  // 提前剪枝
            }
            currentSum += n;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        System.out.println(sol.splitArray(new int[]{7,2,5,10,8}, 2)); // 18
        System.out.println(sol.splitArray(new int[]{1,2,3,4,5}, 2)); // 9
        System.out.println(sol.splitArray(new int[]{1,4,4}, 3)); // 4
    }
}

复杂度分析

  • 时间复杂度：O(n log S)，S = sum(nums)。
  • 空间复杂度：O(1)。

四、解法三最优：对比与深度解析

两种解法的对比

维度动态规划二分答案+贪心
时间复杂度O(n²m)O(n log S)
空间复杂度O(nm)O(1)
思维难度中等（DP 状态设计）较高（需要想到二分答案）
代码难度较高较低
推荐场景m 很小时效率可接受大数据量，首选

为什么贪心验证是正确的（严格证明）

命题： 给定最大和上限 maxSum，最少需要 minParts(maxSum) 组。canSplit(maxSum, m) 返回 minParts(maxSum) <= m。

证明贪心给出的 parts 就是 minParts：

假设存在一种分法使得组数 < parts_greedy，则必然存在某组包含的元素，在贪心中会导致需要新开一组，但在最优方案中不需要。

反证：若最优方案的某个切割点比贪心早（更靠左），则该组包含的元素比贪心方案少，后续面对相同的剩余元素，至少需要同等的组数。所以贪心不会比最优方案更差。

贪心切割是"尽量推迟切割"，因此给后续最大空间，组数最少。得证。

Mermaid 图：贪心验证流程

完整代码（最终优化版）

public class Solution3 {
    public int splitArray(int[] nums, int m) {
        long left = 0, right = 0;
        for (int n : nums) {
            left = Math.max(left, n);  // 下界：单个元素最大值
            right += n;                // 上界：所有元素之和
        }

        // 二分答案：找最小的 maxSum，使得能以不超过 m 组划分
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (minPartsNeeded(nums, mid) <= m) {
                right = mid;      // mid 可行，尝试更小的答案
            } else {
                left = mid + 1;   // mid 不可行，答案更大
            }
        }
        return (int) left;
    }

    /**
     * 贪心计算：以 maxSum 为上限，最少需要几组
     * 策略：每组尽量多装，不超过 maxSum 为止
     */
    private int minPartsNeeded(int[] nums, long maxSum) {
        int parts = 1;
        long current = 0;
        for (int n : nums) {
            if (current + n > maxSum) {
                parts++;
                current = 0;
            }
            current += n;
        }
        return parts;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        System.out.println(sol.splitArray(new int[]{7, 2, 5, 10, 8}, 2)); // 18
        System.out.println(sol.splitArray(new int[]{1, 2, 3, 4, 5}, 2)); // 9
        System.out.println(sol.splitArray(new int[]{1, 4, 4}, 3)); // 4

        // 边界：m == n，每个元素一组
        System.out.println(sol.splitArray(new int[]{1, 2, 3, 4, 5}, 5)); // 5

        // 边界：m == 1，整个数组一组
        System.out.println(sol.splitArray(new int[]{1, 2, 3, 4, 5}, 1)); // 15
    }
}

复杂度分析

  • 时间复杂度：O(n log S)，S = sum(nums)。
    • log(sum) 最大约 log(10^9) ≈ 30 次
    • 每次 canSplit 是 O(n)
    • 总计 O(30n)
  • 空间复杂度：O(1)。

五、举一反三

题号题目对应关系
875珂珂吃香蕉"速度" 对应 "最大子数组和"
1011D天内送达包裹完全相同框架
1891割绳子"最大化最小长度" 版本
2271毯子覆盖的最多白色砖块数二分 + 前缀和验证

六、踩坑实录

坑一：下界设置错误

下界必须是 max(nums)，不能是 0 或 1。如果下界小于 max(nums)，贪心验证函数在处理最大元素时就会失败——因为单个元素已经超过了 maxSum，贪心会把它单独分一组，组数计算错误。

坑二：数据类型用 int 导致溢出

nums[i] 最大 10^8，长度最大 1000，sum 最大 10^11，远超 int 范围。right 必须用 long。这个坑我在第一次提交时就踩了，Wrong Answer 后检查发现 right 溢出成了负数，二分完全失效。

坑三：m == 1 和 m == n 的边界

  • m == 1：只有一组，答案就是 sum(nums)，二分也能给出正确答案（right 初始就是 sum(nums)，且 canSplit 在 maxSum == sum 时必返回 true）。
  • m == n：每个元素一组，答案就是 max(nums)，二分也能正确处理（left 初始就是 max(nums)，是最优答案）。

边界情况不需要特判，通用逻辑都能覆盖。

坑四：贪心里忘记更新 current

与 1011 一样，新开一组时必须 current = 0 再 current += nums[i]。不能先加后切，否则当前元素会消失。

坑五：二分上界设置为 Integer.MAX_VALUE 导致中点溢出

有人为了"安全"把 right 设为 Integer.MAX_VALUE，但这样 left + right 在 mid 的计算中会溢出（即使 left 和 right 都用 long 存储，也要注意）。用精确的 sum(nums) 作为上界，既安全又不浪费。

七、总结

LeetCode 410 是"二分答案 + 贪心验证"这个组合拳的最经典代表。这道题的 Hard 难度，很大程度上来自于需要想到"答案空间上二分"这个非直觉的跳跃。

一旦想到了这个方向，后面的贪心验证其实是直觉的——尽量多装，装不下了换一组，统计组数。贪心正确性的证明也不复杂：贪心是"尽量推迟切割"，给后面最大空间，所以组数最少。

掌握了这道题，加上 875 和 1011，你对"二分答案"这个思路就有了完整的认识。面试中遇到"最小化最大值"或"最大化最小值"类型的题目，第一个念头就应该是：能不能二分答案？

编辑此页
最近更新:
贡献者: xiaozhangge