Split Array Largest Sum

Partition an array into k subarrays to minimize the largest subarray sum.

dynamic-programming binary-search arrays optimization

Given a non-empty array `nums` of non-negative integers and an integer `k` (1 ≤ k ≤ len(nums)), you need to split `nums` into exactly `k` contiguous non-empty subarrays such that the maximum sum among these subarrays is minimized.

Implement the function `split_array_largest_sum(nums, k)` that returns the minimized largest sum.

**Examples:**
- `split_array_largest_sum([7,2,5,10,8], 2)` returns `18` (splitting as `[7,2,5]` and `[10,8]` gives max sum 18).
- `split_array_largest_sum([1,2,3,4,5], 2)` returns `9`.
- `split_array_largest_sum([1,4,4], 3)` returns `4`.

You can assume the sum of all elements fits in a Python integer (no overflow issues).

Constraints

- `1 <= len(nums) <= 1000`
- `0 <= nums[i] <= 10^4`
- `1 <= k <= len(nums)`
- The total sum of `nums` may be up to 10^7.

Solutions of O(n*k*log(sum)) (binary search) or O(k*n^2) (DP) are acceptable within the constraints.

Example

>>> split_array_largest_sum([7,2,5,10,8], 2)
18
>>> split_array_largest_sum([1,2,3,4,5], 2)
9
>>> split_array_largest_sum([1,4,4], 3)
4
>>> split_array_largest_sum([5,5,5], 1)
15

45 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about using binary search on the possible largest sum value.

For a given candidate sum `mid`, greedily check if you can split `nums` into at most `k` subarrays each with sum ≤ `mid`.

Alternatively, define dp[i][j] = min largest sum for first i elements split into j parts.

Try to optimize the greedy check to be O(n), then binary search runs in O(n log(total_sum)).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.