1215. Split Array Largest Sum (Binary Search + DP)

Given an array nums of non-negative integers and an integer k, split nums into k non-empty contiguous subarrays to minimize the largest subarray sum. Return that minimized largest sum. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Integer — the minimized largest subarray sum.

Examples

Input: {"nums":[7,2,5,10,8],"k":2}
Output: 18
Explanation: [7,2,5] and [10,8].

Input: {"nums":[1,2,3,4,5],"k":2}
Output: 9
Explanation: [1,2,3,4] and [5].

Input: {"nums":[5],"k":1}
Output: 5
Explanation: Single subarray.

Constraints

• 1<=n<=1000
• 1<=k<=n

Asked by