Split Array Largest Sum

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 of the split.

Examples

Example 1:

Input: nums = [7, 2, 5, 10, 8], k = 2

Output: 18

Explanation: The best split is [7, 2, 5] and [10, 8], where the largest sum is 18.

Example 2:

Input: nums = [1, 2, 3, 4, 5], k = 2

Output: 9

Explanation: The best split is [1, 2, 3] and [4, 5], with largest sum 9.

Example 3:

Input: nums = [1, 4, 4], k = 3

Output: 4

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)