⚡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