Split Array Largest Sum

Hard· binary search on answer· greedy check

Problem

Split an array of non-negative integers into exactly k non-empty contiguous pieces. Among all ways to do it, minimise the largest piece sum and return that minimum.

Examples

Input: nums = [7,2,5,10,8], k = 2

Output: 18

Splitting into [7,2,5] and [10,8] gives sums 14 and 18; no split does better.

Input: nums = [1,4,4], k = 3

Output: 4

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

Hints & approach

Hint 1

Flip the question: given a limit L, can you split into at most k pieces each summing to at most L?

Hint 2

That check is a single greedy pass.

Hint 3

The answer lies between max(nums) and sum(nums); binary search it.

Approachtry the hints first

Guess a cap L on the largest piece and ask whether the array can be cut into at most k pieces that respect it. Greedily extend the current piece until adding the next element would exceed L, then start a new piece; count the pieces. If the count is at most k, L is achievable (fewer pieces can always be split further since values are non-negative), so search lower; otherwise search higher. Binary search L over [max(nums), sum(nums)]. This is the same shape as the ship-capacity problem and beats the O(k n^2) DP.

Time O(n log S), S = sum of nums · Space O(1)

← PreviousCapacity To Ship Packages Within D Days Next →Median of Two Sorted Arrays