Minimize Maximum Sum Partition

Minimize Maximum Sum Partition

You are given a list of n integers and an integer k. Your task is to divide the list into exactly k contiguous subarrays such that the maximum sum among these subarrays is minimized.

Formally, given an array \(a_1, a_2, \ldots, a_n\), you need to partition it into k contiguous segments \(S_1, S_2, \ldots, S_k\). Let \(M = max(sum(S_1), sum(S_2), \dots, sum(S_k))\). The goal is to minimize \(M\).

This problem can be solved efficiently with a binary search approach combined with a greedy strategy to test if a given value can be a valid maximum sum partitioning.

inputFormat

The first line of input contains two integers n and k separated by a space, where n is the number of elements in the array and k is the number of contiguous subarrays to partition into.

The second line contains n space-separated integers representing the array elements.

Input Format (stdin):

n k
 a1 a2 a3 ... an

outputFormat

Output a single integer, which is the minimum possible value of the maximum sum among the k contiguous subarrays.

Output Format (stdout):

result

## sample

7 3
7 2 5 10 8

14