Minimized Maximum Subarray Sum Partitioning

Alex is given an array of positive integers \(a_1, a_2, \ldots, a_n\) and he wants to split this array into exactly \(k\) non-empty contiguous subarrays. The goal is to partition the array such that the maximum sum among these subarrays is minimized. In other words, if the subarrays have sums \(S_1, S_2, \ldots, S_k\), we want to minimize \(\max(S_1, S_2, \ldots, S_k)\).

Task: Given the integer \(n\), the number \(k\), and the array of \(n\) positive integers, compute the minimized maximum sum achievable by splitting the array into exactly \(k\) contiguous subarrays.

Hint: You may use binary search on the answer. The valid range lies between \(\max(a_i)\) and \(\sum_{i=1}^n a_i\). Check for a candidate value \(M\) if it is possible to partition the array into at most \(k\) parts where each part has a sum at most \(M\).

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space.

The second line contains \(n\) space-separated positive integers representing the array elements \(a_1, a_2, \ldots, a_n\).

outputFormat

Output a single integer which is the minimized maximum subarray sum after partitioning the array into exactly \(k\) contiguous subarrays.

5 2
1 2 3 4 5

9