Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Split Array Largest Sum

LeetCode #410Hard
Binary search the cap · greedy feasibility

Given an array of non-negative integers and an integer k, split the array into k non-empty contiguous subarrays so that the largest subarray sum is minimized, and return that minimized largest sum.

Asked atGoogleAmazon
step 1 / 14
7
2
5
10
8
[0][1][2][3][4]
Brute force · try every cut
▸
1given arr, m = 2
2for each cut position:
3    largest = max(sum left, sum right)
4return the minimum largest
state
  • m2
  • total32

line 1Split the array into m = 2 CONTIGUOUS pieces, minimizing the LARGEST piece-sum. (Fair workload split: nobody's share too heavy.) With m = 2 there are only n − 1 = 4 cut positions — try them all.