487. Split Array Largest Sum

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

Input: '[arr], k'.

Output: Integer — the minimized largest subarray 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: [1,2,3] and [4,5].

Input: [1], 1
Output: 1
Explanation: Single subarray.

Constraints

• 1<=n<=1000
• 0<=value<=10^6
• 1<=k<=n

Asked by