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.
numsk representing the number of contiguous partsAssume the array is provided in the usual interview/LeetCode style.
Return the minimum possible value of the largest subarray sum after splitting the array into exactly non-empty contiguous subarrays.
1 <= k <= nums.lengthk non-empty contiguous partsExample 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.
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
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.