Description
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum.
Examples
Input:
nums = [7,2,5,10,8], k = 2Output:
18Explanation:
Split as [7,2,5] and [10,8]. Largest sum is max(14, 18) = 18.
Input:
nums = [1,4,4], k = 3Output:
4Explanation:
With k=3 and array length 3, each element forms its own subarray: [1], [4], [4]. The largest subarray sum is max(1, 4, 4) = 4.
Input:
nums = [2,3,1,2,4,3], k = 4Output:
4Explanation:
The optimal split minimizes the largest subarray sum. Splitting as [2,3,1], [2,4], [3] gives sums 6, 6, 3 with maximum 6. No other 4-way split achieves a smaller maximum. Splitting into 4 subarrays and minimizing the largest subarray sum yields 5.
Constraints
- •
1 ≤ nums.length ≤ 1000 - •
0 ≤ nums[i] ≤ 10⁶ - •
1 ≤ k ≤ min(50, nums.length)