#410
Split Array Largest Sum
expert · 1180 · lc hard +32 · verified · 59.9% accepted · 11,259 likes · top 58%
Description
Given an integer array nums and integer k, partition nums into exactly k non-empty contiguous subarrays to make the largest subarray sum as small as possible. Return that minimized maximum subarray sum.
Example 1:
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
Example 2:
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
Code
1
2
3