Split Array Largest Sum

HARD✓ CHIP-TIMEDLC #410 — FULL STATEMENT ↗

The drill: Cut an array into k contiguous, non-empty pieces so the heaviest piece is as light as possible — return that minimized largest-piece sum across the best split.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of non-negative integers needs to be cut into exactly k contiguous, non-empty pieces — no skipping elements, no piece left empty, and the original order of elements never changes.

Every possible way of making those k cuts produces some set of piece sums, and each split has a worst piece — the single largest sum among its pieces.

The job is to choose the split that makes that worst piece as small as possible, and report the sum of that piece under the best possible split.

EX 01

nums = [3, 1, 4, 1, 5, 9, 2, 6] · k = 3

→ 14

BEST SPLIT IS [3,1,4,1,5]=14, [9,2]=11, [6]=6

EX 02

nums = [2, 4, 6, 8] · k = 1

→ 20

K=1, THE WHOLE ARRAY IS THE ONLY PIECE

EX 03

nums = [5, 1, 9, 2] · k = 4

→ 9

K=N, EVERY ELEMENT IS ITS OWN PIECE

array holds up to a few thousand non-negative integers
k is always at least one and never exceeds the array length
every piece must be contiguous and non-empty
only the minimized largest-piece sum is expected back, not the split itself

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A DP over “first i elements split into j pieces” finds the exact minimum, but it explores every cut point. What if, instead of building the split, you guessed its answer and only checked whether that guess works?

HINT 2 THE STRUCTURE

For a candidate cap M, greedily pack elements left to right until adding one would overflow M, then start a new piece — that greedy count is the fewest pieces possible under M, and it only grows as M shrinks.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search M between the largest single element and the total sum: if the greedy piece count for M fits within k, M is big enough — shrink the search; otherwise M is too small — grow it.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FAIREST SPLITPATTERN · BINARY SEARCH THE ANSWERnums = [3, 1, 4, 1, 5, 9, 2, 6] · k = 3

BINARY SEARCH ON THE CAP

— empty —

STEP 1

8 elements split into k=3 contiguous pieces. Binary-search the cap on the largest piece, between 9 (the max element) and 31 (the total).

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/split-array-largest-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def pieces_needed(cap: int) -> int:
            pieces, current = 1, 0
            for v in nums:
                if current + v > cap:
                    pieces += 1
                    current = v
                else:
                    current += v
            return pieces

        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if pieces_needed(mid) <= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

TIME O(N·LOG(SUM−MAX))SPACE O(1)PYTHON · RACE PACE · 20 LN

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i, v in enumerate(nums):
            prefix[i + 1] = prefix[i] + v

        INF = float("inf")
        # dp[j][i] = best achievable "largest piece" splitting the first i
        # elements into exactly j pieces
        dp = [[INF] * (n + 1) for _ in range(k + 1)]
        dp[0][0] = 0
        for j in range(1, k + 1):
            for i in range(j, n + 1):
                for p in range(j - 1, i):        # the previous cut lands at p
                    if dp[j - 1][p] == INF:
                        continue
                    piece = prefix[i] - prefix[p]
                    candidate = max(dp[j - 1][p], piece)
                    if candidate < dp[j][i]:
                        dp[j][i] = candidate
        return dp[k][n]

TIME O(N²·K)SPACE O(N·K)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0, hi = 0;
        for (int v : nums) {
            lo = Math.max(lo, v);
            hi += v;
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (piecesNeeded(nums, mid) <= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private int piecesNeeded(int[] nums, int cap) {
        int pieces = 1, current = 0;
        for (int v : nums) {
            if (current + v > cap) {
                pieces++;
                current = v;
            } else {
                current += v;
            }
        }
        return pieces;
    }
}

TIME O(N·LOG(SUM−MAX))SPACE O(1)JAVA · RACE PACE · 31 LN

class Solution {
    public int splitArray(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int INF = Integer.MAX_VALUE;
        int[][] dp = new int[k + 1][n + 1];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        dp[0][0] = 0;
        for (int j = 1; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int p = j - 1; p < i; p++) {
                    if (dp[j - 1][p] == INF) {
                        continue;
                    }
                    int piece = prefix[i] - prefix[p];
                    int candidate = Math.max(dp[j - 1][p], piece);
                    if (candidate < dp[j][i]) {
                        dp[j][i] = candidate;
                    }
                }
            }
        }
        return dp[k][n];
    }
}

TIME O(N²·K)SPACE O(N·K)JAVA · TRAINING PACE · 31 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED