Split Array Largest Sum

Q: What is the time complexity of Split Array Largest Sum?

O(n log S) time and O(1) extra space, where S is the sum of nums : each greedy check is one pass, and the range of caps halves after each check. That is about 29 checks when S = 5 × 10^8 . The DP takes O(k·n²) time.

Q: Why is the feasibility check monotonic?

If every part of a split sums to at most c , the same split fits under c+1 . So once a cap works, every larger cap works, and the answers form a run of no followed by a run of yes. Binary search finds the first yes.

Q: Does the binary search work with negative numbers?

No. A negative value can lower a sum, so greedy may close a part too early, and splitting a part can raise one piece above the whole. The DP makes neither assumption and stays correct.

HardBinary search Dynamic programming

+10

You get an array nums of non-negative integers and an integer k. Cut nums into exactly k parts, where each part is a non-empty run of neighbouring values and the parts keep their order. Every part has a sum, and the cost of a split is the largest of those sums.

Return the smallest cost that any split into k parts can reach.

Function

splitArray(nums: integer-array, k: integer) → integer

numsinteger-array: the non-negative values, in order
kinteger: the number of contiguous parts to cut them into
Returnsinteger: the smallest possible value of the largest part sum

Constraints

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Every part holds at least one value. A part whose values are all 0 sums to 0, which is allowed.

Examples

Input: nums = [6, 2, 9, 4, 7, 3]k = 3
Output: 13
Explanation: The split [6, 2], [9, 4], [7, 3] costs 13. No split costs 12: packing parts left to right under 12 gives [6, 2], [9], [4, 7], [3], four parts.

Input: nums = [8, 1, 1, 1, 5]k = 2
Output: 8
Explanation: The 8 sits in some part, so no split can cost less than 8. [8] and [1, 1, 1, 5] both sum to 8.

Follow-up

With prefix sums, a greedy check can find where each part ends by binary search. How fast does the whole method get when k is small?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Searching for the best split directly costs O(k·n²) even with dynamic programming. Turn the question around: can k parts stay under a given cap? One greedy pass answers that, the answer flips from no to yes once as the cap grows, and binary search finds the flip.

Dynamic programming over prefixes

Correct, but does not finish on the largest tests

Intuition

Write best[p][j] for the smallest cost of cutting the first j values into p parts. If the last part is nums[i..j-1], the cost is the larger of best[p-1][i] and that part's sum, and the best split of the first i values does not depend on anything to its right. So best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), with i from p-1 to j-1 so every part holds a value. Row p only reads row p-1, so two rows are enough.

It runs up to k·n²/2 steps: about 1.8 × 10^10 for n = 5000 and k = 2500.

Algorithm

Build prefix, where prefix[j] is the sum of the first j values, and set best[j] = prefix[j] for one part.
For each part count p from 2 to k, and each end j from p to n, take the minimum over i from p-1 to j-1 of max(best[i], prefix[j] - prefix[i]).
Store those minimums in a new row and make it best.
Return best[n].

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

Binary search on the largest sum

Intuition

To test a cap c, walk left to right and add values to the current part while its sum stays within c, then start a new part. This uses the fewest parts possible. Against any valid split, greedy's first part ends at least as far right, so its next part starts at or after the other's. Its values up to that part's end are a piece of a part that fits, and with no negative values a piece never sums to more than the whole. So greedy never falls behind.

Fewer than k parts is as good as k: cutting a part of two or more values into two never raises a sum. So the test is partsNeeded(c) ≤ k.

Binary search the smallest passing cap between max(nums), since that value sits in some part, and sum(nums), which always fits in one part.

Algorithm

Set lo = max(nums) and hi = sum(nums).
While lo < hi, take mid = lo + (hi - lo) / 2.
Count greedy parts under mid: start at 1 part with sum 0; when adding a value would pass mid, add a part and restart the sum at that value.
If the count is at most k, set hi = mid; otherwise set lo = mid + 1.
Return lo.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

Pitfalls and edge cases

Starting lo below max(nums). Greedy puts a value larger than the cap in a part of its own, so it reports cap 5 as fine for [1, 9] with k = 2.
Testing partsNeeded(c) == k. For [3, 0, 4] and k = 3, cap 4 packs [3, 0], [4], so no cap ever passes.
Counting parts from 0, which makes every count one too small.
Setting hi = mid - 1 when mid works, which loses the answer when it is mid.
Starting the DP's i at 0. A cell with fewer values than parts reads as cost 0, and [100, 1, 1] with k = 3 reports 2 instead of 100.

Frequently asked questions3

What is the time complexity of Split Array Largest Sum?

O(n log S) time and O(1) extra space, where S is the sum of nums: each greedy check is one pass, and the range of caps halves after each check. That is about 29 checks when S = 5 × 10^8. The DP takes O(k·n²) time.

Why is the feasibility check monotonic?

If every part of a split sums to at most c, the same split fits under c+1. So once a cap works, every larger cap works, and the answers form a run of no followed by a run of yes. Binary search finds the first yes.

Does the binary search work with negative numbers?

No. A negative value can lower a sum, so greedy may close a part too early, and splitting a part can raise one piece above the whole. The DP makes neither assumption and stays correct.

def splitArray(nums, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

nums = [6, 2, 9, 4, 7, 3]
k = 3

Expected Output