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. Input The first input line contains two integers � n and � k: the size of the array and the number of subarrays in the division. The next line contains � n integers � 1 , � 2 , … , � � x 1 ​ ,x 2 ​ ,…,x n ​ : the contents of the array. Output Print one integer: the maximum sum in a subarray in the optimal division. Constraints 1 ≤ � ≤ 2 ⋅ 1 0 5 1≤n≤2⋅10 5 1 ≤ � ≤ � 1≤k≤n 1 ≤ � � ≤ 1 0 9 1≤x i ​ ≤10 9 Explanation: An optimal division is [ 2 , 4 ] , [ 7 ] , [ 3 , 5 ] [2,4],[7],[3,5] where the sums of the subarrays are 6 , 7 , 8 6,7,8. The largest sum is the last sum 8 8.

This problem can be solved using binary search. We can try to find the minimum possible maximum sum in a subarray by binary searching over the range of possible values. The upper bound of this range is the sum of all elements in the array, since each subarray must have at least one element. The lower bound of this range is the maximum element in the array, since each subarray must have at least one element and the maximum element must be in its own subarray.

For each guess of the maximum sum, we can try to divide the array into subarrays such that no subarray has a sum greater than the guess. This can be done by iterating through the array and greedily assigning each element to the current subarray until the sum of the subarray is greater than the guess. Then, we start a new subarray with the current element.

If we can divide the array into k subarrays with a maximum sum no greater than our guess, we can try a smaller guess. If we cannot divide the array into k subarrays with a maximum sum no greater than our guess, we need to try a larger guess.

Here's some sample code in Python:

n, k = map(int, input().split())
arr = list(map(int, input().split()))

low = max(arr)
high = sum(arr)

while low < high:
    mid = (low + high) // 2
    count = 1
    total = 0
    for x in arr:
        if total + x > mid:
            count += 1
            total = x
        else:
            total += x

    if count > k:
        low = mid + 1
    else:
        high = mid

print(low)

This code reads in the input and initializes the range of possible values for the maximum sum in a subarray. Then, it performs binary search to find the minimum possible maximum sum. For each guess of the maximum sum, it tries to divide the array into k subarrays such that no subarray has a sum greater than the guess. If it can do this, it tries a smaller guess. If not, it tries a larger guess. Finally, it prints out the minimum possible maximum sum.