Split Array to Minimize Maximum Subarray Sum

You are given an array of non-negative integers and an integer k. Your task is to split the array into k contiguous subarrays such that the largest sum among these subarrays is minimized. Formally, if you partition the array A = [a_1, a_2, \dots, a_n] into k parts, let the sum of the i-th subarray be \(S_i\). You need to minimize \(\max(S_1, S_2, \dots, S_k)\).

Hint: A binary search combined with a greedy check can be used to decide if a candidate maximum sum can partition the array into at most k parts.

inputFormat

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers, which are the elements of the array.

The third line contains an integer k representing the number of subarrays to split the array into.

outputFormat

Output a single integer, the minimized largest sum among the k subarrays after partitioning the array.

5
7 2 5 10 8
2

18