Split into k Segments, Maximise the Lightest

Given positive integers values and an integer k, split the list into exactly k contiguous, non-empty segments so that the smallest segment sum is as large as possible. Return that smallest segment sum.

Examples

Input:  values = [1, 2, 3, 4, 5], k = 2
Output: 6
Explanation: [1, 2, 3] | [4, 5] has segment sums 6 and 9; no split does better than 6.

Input:  values = [5, 5, 5, 5], k = 4
Output: 5

Input:  values = [1, 1, 1, 10], k = 2
Output: 3

Constraints

• 1 <= k <= len(values) <= 3 * 10**4
• 1 <= values[i] <= 10**6
• Required time: O(n log(sum(values))).

Goals

• Flip the search direction: find the largest value that is still feasible
• Justify why a greedy count of 'full' segments is enough