Partition Array to Minimize Largest Sum

You are given an array of positive integers and an integer k. Your task is to partition the array into k non-empty contiguous subarrays such that the maximum sum among these subarrays is minimized.

Formally, if the array is \(a_1, a_2, \ldots, a_n\) and it is partitioned into k subarrays \(S_1, S_2, \ldots, S_k\), you need to minimize the quantity \(\max_{1 \leq i \leq k} \sum_{a \in S_i} a\). This problem can be efficiently solved via binary search combined with a greedy verification strategy.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains two space-separated integers n and k, where n is the number of elements in the array (n ≥ k), and k is the number of subarrays to partition into.
• The second line contains n space-separated positive integers representing the array elements.

outputFormat

Output a single integer to standard output (stdout) representing the minimized maximum subarray sum after partitioning.

5 2
7 2 5 10 8

18