134. Split Array Largest Sum

Given an array nums and integer k, split it into k non-empty contiguous subarrays to minimize the largest subarray sum. Return that minimized largest sum. Input: '[nums], k'.

Input: '[nums], k'.

Output: Integer — minimized largest sum.

Examples

Input: [7,2,5,10,8], 2
Output: 18
Explanation: Split [7,2,5] and [10,8].

Input: [1,2,3,4,5], 2
Output: 9
Explanation: Split [1,2,3,4] and [5].

Input: [1,4,4], 3
Output: 4
Explanation: Each element separate.

Constraints

• 1<=n<=1000
• 1<=k<=n
• 0<=nums[i]<=10^6

Asked by