Minimum Maximum Sum
Given an array A of N non-negative integers and an integer K, partition the array into K contiguous subarrays. Your goal is to minimize the largest sum among these K subarrays. Find this minimum possible largest sum.
Input
The first line contains two integers N and K. The second line contains N non-negative integers A_1, A_2, ..., A_N.
Output
Print a single integer: the minimum possible largest sum of any subarray in the partition.
Constraints
1 <= N <= 200000, 1 <= K <= N, 0 <= A_i <= 10^9. The sum of all elements will not exceed 10^15.
Example 1
5 2 1 2 3 4 5
9
Partition into [1, 2, 3] and [4, 5]. Max sum is 9. Partitions [1,2] and [3,4,5] give max sum 12. The minimum max sum is 9.
Example 2
4 3 10 5 15 20
20
Partitions like [10], [5], [15, 20] give max sum 35. Partitions [10], [5, 15], [20] give max sum 25. The minimum max sum is 25.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 1 2 3 4 5
4 3 10 5 15 20