Split Array Largest Sum

Binary Search, problem 7 of 7

Split Array Largest Sum

Hard

LC #410

binary search on answergreedy

Not attempted yet

Given a non-negative integer array nums and an integer k, split nums into exactly k non-empty contiguous subarrays so that the largest subarray sum is as small as possible.

Return that minimised largest sum.

Example 1

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: [7,2,5] | [10,8] gives
max(14, 18) = 18, the best possible.

Example 2

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: [1,2,3] | [4,5]

Example 3

Input: nums = [1,4,4], k = 3
Output: 4

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= nums.length

Python

Loading draft…

Test results

9 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 6 hidden

Run examples, then submit all tests.