Dashboard
LC #410

Split Array Largest Sum

Pattern · ?GoogleMetaAmazonBloomberg

Problem

Split an array into k non-empty subarrays to minimize the largest subarray sum.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • 0 ≤ nums[i] ≤ 10⁶
  • 1 ≤ k ≤ min(50, nums.length)

Example

Input
nums = [7, 2, 5, 10, 8], k = 2
Output
18
Why
Split into [7,2,5] and [10,8] → max sum 18. Or [7,2,5,10] and [8] → 24. Best is 18.

Spot the pattern

Which pattern cracks it?

Hints

One at a time
Solve on LeetCode ↗