⚡Flashcard Drill➔
NeetCode #297LC-410HardBinary SearchNC 250
← Back to All Problems

#297 · #410 · Split Array Largest Sum(分割数组的最大值)

📌 Problem Statement & Constraints

Given an array nums of non-negative integers and an integer k, split the array into k non-empty contiguous subarrays so that the largest subarray sum is minimised. Return that minimum largest sum. Constraints: 1 <= nums.length <= 1000, 0 <= nums[i] <= 10^6, 1 <= k <= min(50, nums.length).

💡 Core Algorithmic Approaches

  1. Binary search on the answer: the predicate "can split into at most k parts each with sum at most c" is monotone in c.
  2. The lower bound is max(nums) (a single element must fit) and the upper bound is sum(nums).
  3. For a given c, greedily accumulate until adding the next element would exceed c, then start a new part.
  4. If the number of parts is at most k, the capacity is feasible.

💻 Benchmark Python3 Implementation

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            parts = 1
            cur = 0
            for x in nums:
                if cur + x > mid:
                    parts += 1
                    cur = 0
                cur += x
            if parts <= k:
                hi = mid               # feasible -> try smaller
            else:
                lo = mid + 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log(sum(nums))): each predicate is O(n).
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using DP instead: the DP is O(n^2 * k) and much more code; the binary-search-on-answer approach is O(n log V).
  • Setting the lower bound to 0: a part must contain at least one element, so max(nums) is the tight lower bound.
  • Using parts < k instead of parts <= k: using fewer parts than k is acceptable (extra parts can be split further), so the condition is <=.
  • Forgetting that subarrays must be contiguous: that is exactly why the greedy works.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems

中文速览与面试要点

分割数组的最大值

给定一个非负整数数组 nums 和一个整数 k,你需要将这个数组分成 k 个 非空 的连续子数组。设计一个算法使得这 k 个子数组各自和的最大值 最小 。返回这个最小的最大值。约束:1 ≤ nums.length ≤ 1000;0 ≤ nums[i] ≤ 10^6;1 ≤ k ≤ min(50, nums.length)。

核心要点

  • 二分答案(标准解) :二分「子数组和的上限 limit」,判定「能否用不超过 limit 的容量把数组分成 ≤ k 段」。
  • 单调性 :limit 越大越容易满足(段数越少),因此可以二分。
  • 判定函数 :贪心累加,超过 limit 就开新段。返回段数是否 ≤ k。
  • 答案范围 : [max(nums), sum(nums)] 。下界是单个元素的最大值,上界是整个数组的和。
  • 与 1011 完全同构 :本题是「在 D 天内送达」的抽象版本,判定函数几乎一致。

常见陷阱

  • 下界写成 0 或 1 :nums[i] 可以为 0,但下界仍应取 max(nums) (保证单元素能放进一段)。
  • 判定条件写成 == k :贪心得到的段数是「在 limit 下的最少段数」,若它 ≤ k,则总可以通过进一步切分得到恰好 k 段(因为允许空?不,题目要求非空段——但段数更少时可以继续切分,只要段数 ≤ k 且元素数 ≥ k 即可,题目约束保证了这一点)。因此判定应为 &lt;= k 。
  • 用 DP 求解 : dp[i][j] 表示前 i 个元素分成 j 段的最小最大值,复杂度 O(n² k)。n = 1000 时约 5 × 10^7,可能超时;二分答案只需 O(n log(sum))。
  • 二分方向写反 :本题求「最小的最大和」,应写 if feasible: r = mid 。

参考实现

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def segments_needed(limit: int) -> int:
            cnt = 1
            cur = 0
            for x in nums:
                if cur + x > limit:
                    cnt += 1
                    cur = 0
                cur += x
            return cnt

        l, r = max(nums), sum(nums)
        while l < r:
            mid = (l + r) // 2
            if segments_needed(mid) <= k:
                r = mid                 # 可行 -> 尝试更小的上限
            else:
                l = mid + 1
        return l