Array Division

mediumBinary Searcharrays

You are given an array containing $$$n$$$ positive integers.

Your task is to divide the array into $$$k$$$ subarrays so that the maximum sum in a subarray is as small as possible.

Note that each element of the array must belong to exactly one subarray, and the subarrays must be contiguous (you cannot skip elements).

Input Format:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$): the size of the array and the number of subarrays in the division.

The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$): the contents of the array.

Output Format:

Print one integer: the maximum sum in a subarray in the optimal division.

Examples:

Example 1:

Input:

5 3
2 4 7 3 5

Output:

8

Example 2:

Input:

4 3
1 2 3 4

Output:

4

Note:

In the first test case, an optimal division is $$$[2, 4], [7], [3, 5]$$$, where the sums of the subarrays are $$$6, 7, 8$$$. The largest sum is the last sum, $$$8$$$.

Code

Loading Editor...