531. Split Array Largest Sum (Optimal)

Given an array and an integer k, split it into k non-empty contiguous subarrays so that the largest subarray sum is minimized, and return that minimized largest sum. This is the optimal O(n log(sum)) binary-search-on-answer formulation. 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<=10^4
• 0<=value<=10^6
• 1<=k<=n

Asked by