Minimize Sum of Maximums

You are given an array of n integers \(nums\) and an integer \(k\). Your task is to partition the array into \(k\) non-empty contiguous subarrays such that the following condition is satisfied:

For each contiguous subarray, define its cost as the maximum element in that subarray. You need to find the minimum possible threshold \(T\) such that the array can be partitioned into at most \(k\) subarrays with the property that in each subarray, the maximum element does not exceed \(T\). In other words, you want to minimize \(T\) subject to a valid partition existing.

Note: Since each subarray is contiguous and non-empty, the minimum possible \(T\) is at least \(\max(nums)\), and an upper bound can be \(\sum_{i=1}^{n} nums_i\). You are expected to apply a binary search strategy over the possible thresholds to determine the optimal value.

Example:

Input: nums = [1, 3, 2, 5, 8, 7, 4], k = 3
Output: 8

Explanation: The minimum threshold allowing the partition into 3 subarrays is 8. One possible partition is such that every subarray’s maximum does not exceed 8.

inputFormat

The first line 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 partitions required.

The second line contains \(n\) integers representing the elements of the array.

Input Format:

n k
nums[0] nums[1] ... nums[n-1]

outputFormat

Output a single integer representing the minimum possible threshold \(T\) such that the array can be partitioned into at most \(k\) contiguous subarrays with each subarray's maximum value \(\le T\).

Output Format:

T

## sample

7 3
1 3 2 5 8 7 4

8