Split Array Largest Sum

Solve it directly as a DP over two dimensions: how many subarrays we have used so far, and how many elements we have consumed. Let dp[j][i] be the minimal possible largest segment sum when the first i elements are split into exactly j contiguous subarrays. The recurrence tries every possible last cut: split off a trailing segment nums[t..i) whose sum is pref[i] - pref[t], and combine it with the best split of the leading t elements into j - 1 subarrays.

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        n = len(nums)
        pref = [0] * (n + 1)
        for i, x in enumerate(nums):
            pref[i + 1] = pref[i] + x
        # dp[j][i]: min largest segment sum splitting first i elements into j segments
        dp = [[float("inf")] * (n + 1) for _ in range(k + 1)]
        for i in range(1, n + 1):
            dp[1][i] = pref[i]  # one segment holds the whole prefix
        for j in range(2, k + 1):
            for i in range(j, n + 1):
                for t in range(j - 1, i):
                    dp[j][i] = min(
                        dp[j][i],
                        max(dp[j - 1][t], pref[i] - pref[t]),
                    )
        return dp[k][n]

For nums = [7,2,5,10,8], k = 2, the base row is dp[1][i] = [7, 9, 14, 24, 32], and the j = 2 row compares every split point t: max(dp[1][1], 32-7)=25, max(9, 23)=23, max(14, 18)=18, max(24, 8)=24 — the minimum is 18, the answer.

Why it is slow: there are k·n states and each one scans up to n candidate cut points, giving O(n²k). The DP table also costs O(nk) space. The approach is correct but pays for exactness it does not need — the full boundary pref array and every intermediate j layer are overkill when all we want is the smallest acceptable cap.

Invert the problem. Instead of computing the optimal split directly, guess a cap and ask the cheap feasibility question: “packed greedily, does this cap fit in k or fewer subarrays?” Greedy is optimal for the feasibility check because to minimize the number of segments under a fixed cap, never start a new segment until the current one would overflow — that uses each cut as late as possible and can never increase the segment count.

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        lo, hi = max(nums), sum(nums)

        def feasible(cap: int) -> bool:
            # Greedy: how many segments are needed when none may sum over cap?
            segments = 1
            cur = 0
            for x in nums:
                cur += x
                if cur > cap:      # overflow: finish this segment, start fresh
                    cur = x
                    segments += 1
            return segments <= k

        while lo < hi:
            mid = (lo + hi) // 2
            if feasible(mid):
                hi = mid          # cap works: look for something smaller
            else:
                lo = mid + 1      # cap fails: every smaller cap fails too
        return lo

Watch the whole search on nums = [7,2,5,10,8], k = 2, where every probe is one greedy pass and the window collapses onto 18:

Why monotonicity is the whole trick. The feasibility check depends on mid going up or down smoothly: raising the cap can only merge adjacent segments, never split one, so once feasible(mid) is true every value above it is true. That turns the search bounds into a hinge — any failing probe raises the floor, any working probe lowers the ceiling — and the loop terminates with lo == hi, the smallest working cap.

Why it is the two-part bound: lo = max(nums) (a subarray must fit its largest element alone), and hi = sum(nums) (one giant subarray always fits). With a binary halving over that range and an O(n) greedy pass per probe, the total is O(n log sum) time and O(1) space — no pref table, no j dimension, just a running sum.