A manager has a list of tasks in a fixed order. nums[i] is the time the i-th task takes. She must split the list into exactly k parts. Each part is a block of tasks that sit next to each other, and no part can be empty. One worker does one part.
The time a part takes is the sum of its tasks. The whole job ends when the slowest worker is done, so you want the largest part sum to be as small as possible.
Return that smallest possible largest sum.
Examples
Example 1:
Input: nums = [6,2,4,3,7], k = 3
Output: 8
Explanation: Split into [6,2], [4,3] and [7]. The sums are 8, 7 and 7. The largest is 8, and no split gives less.
Example 2:
Input: nums = [5,1,5,1,5], k = 2
Output: 11
Explanation: Split into [5,1,5] and [1,5]. The sums are 11 and 6. The largest is 11.
Example 3:
Input: nums = [4,9,2], k = 3
Output: 9
Explanation: There are 3 tasks and 3 workers, so each worker gets one task. The slowest task takes 9.