Split an array into non-empty contiguous parts so that the largest part sum is as small as possible.
Given an integer array, divide it into exactly non-empty contiguous subarrays. Your goal is to minimize the value of the largest subarray sum among the chosen partitioning.
In other words, among all ways to split the array into consecutive groups, return the smallest possible maximum sum of any one group.
Input Format
- An integer array
nums - An integer
krepresenting the number of contiguous parts
Assume the array is provided in the usual interview/LeetCode style.
Output Format
Return the minimum possible value of the largest subarray sum after splitting the array into exactly non-empty contiguous subarrays.
Constraints
1 <= k <= nums.length- Elements are integers
- The array should be split into exactly
knon-empty contiguous parts
Example 1
Input
nums = [7,2,5,10,8], k = 2
Output
18
Explanation
One optimal split is [7,2,5] and [10,8]. Their sums are 14 and 18, so the largest sum is 18. No valid split has a smaller maximum part sum.
Example 2
Input
nums = [1,2,3,4,5], k = 2
Output
9
Explanation
An optimal split is [1,2,3] and [4,5]. The part sums are 6 and 9, so the largest sum is 9.
Show 1 more example
Example 3
Input
nums = [1,4,4], k = 3
Output
4
Explanation
The only valid split is [1], [4], [4], so the largest subarray sum is 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.