Minimum Largest Segment Sum

You are given an array of positive integers values and an integer groups.

Split values into exactly groups non-empty, contiguous segments. The elements keep their original order, and every element belongs to exactly one segment. The cost of a partition is the largest sum among its segments.

Return the minimum possible cost over all valid partitions into groups segments.

Examples

Example 1

Input: values = [1,2,3,4,5,6,7,8,9,10], groups = 5
Output: 15
Explanation: One optimal split is [1,2,3,4,5], [6,7], [8], [9], [10], whose
segment sums are 15, 13, 8, 9, 10. The largest is 15, and no split into 5
contiguous segments achieves a smaller maximum.

Example 2

Input: values = [3,2,2,4,1,4], groups = 3
Output: 6
Explanation: The split [3,2], [2,4], [1,4] has segment sums 5, 6, 5; the
largest is 6.

Example 3

Input: values = [1,2,3,1,1], groups = 4
Output: 3
Explanation: The split [1], [2], [3], [1,1] has segment sums 1, 2, 3, 2; the
largest is 3.