The problem. Given an integer array nums of non-negative values and an integer k, split nums into k non-empty contiguous pieces so that the largest piece sum is as small as possible. Return that smallest possible largest sum.
nums = [7, 2, 5, 10, 8], k = 2 -> 18 ([7, 2, 5] and [10, 8])
nums = [1, 2, 3, 4, 5], k = 2 -> 9 ([1, 2, 3] and [4, 5])
nums = [1, 4, 4], k = 3 -> 4Fix a limit and ask: can the array be cut into at most k pieces, none summing past the limit? Greedy answers it — extend the current piece while it stays within the limit, otherwise start a new one. Fewer than k pieces is fine too, because any piece can be split further without raising the largest sum. A higher limit never needs more pieces, so the answers flip from no to yes once. The limit is at least the biggest value (it has to fit in some piece) and at most the total. This is exactly Capacity To Ship Packages, with pieces for days.
best[j][i] is the smallest largest-sum when the first i values are cut into j pieces. The last piece is nums[p..i−1] for some p, so take the best over all p of the larger of best[j−1][p] and that piece's sum (from prefix sums).
function splitArray(nums, k) { const n = nums.length; const prefix = [0]; for (const x of nums) prefix.push(prefix[prefix.length - 1] + x); const best = Array.from({ length: k + 1 }, () => Array(n + 1).fill(Infinity)); best[0][0] = 0; // zero values in zero pieces for (let j = 1; j <= k; j++) { for (let i = 1; i <= n; i++) { for (let p = j - 1; p < i; p++) { // the last piece is nums[p..i-1] best[j][i] = Math.min(best[j][i], Math.max(best[j - 1][p], prefix[i] - prefix[p])); } } } return best[k][n];}Time O(k · n²), space O(k · n). Correct and a classic DP, but slow for n = 1000 and k = 50.
At each limit, cut the array greedily and count the pieces; at most k means the limit works.
function splitArray(nums, k) { const pieces = (limit) => { // pieces needed if none may sum past limit let count = 1, sum = 0; for (const x of nums) { if (sum + x > limit) { count++; sum = 0; } // start a new piece sum += x; } return count; }; let low = Math.max(...nums); // a piece holds at least the biggest value let high = nums.reduce((a, b) => a + b, 0); // one piece holds everything while (low < high) { const mid = low + Math.floor((high - low) / 2); if (pieces(mid) <= k) high = mid; // possible: try a smaller limit else low = mid + 1; // needs more than k pieces: raise the limit } return low;}Time O(n log(total)), space O(1). The search finds the smallest limit that works, and that limit is always an actual piece sum: if no piece hit it exactly, a smaller limit would work too.
[0, 0, 5] with k = 2: 5.