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
- Binary search on the answer: the predicate "can split into at most
kparts each with sum at mostc" is monotone inc. - The lower bound is
max(nums)(a single element must fit) and the upper bound issum(nums). - For a given
c, greedily accumulate until adding the next element would exceedc, then start a new part. - 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 < kinstead ofparts <= k: using fewer parts thankis 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.