Split Array Largest Sum

Split the array into exactly k non-empty contiguous parts so that the largest part-sum is as small as possible. Print that smallest possible largest sum.

Example: 7 2 5 10 8 with k = 2 → split as 7 2 5 | 10 8 → sums 14 and 18 → answer 18.

Input:

• line 1: n k
• line 2: n integers

Output: the minimised largest sum.

Constraints: 1 ≤ k ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 10⁶.

Think about it: for a candidate limit cap, a greedy pass tells you how many parts you need. Bigger cap → fewer parts. Binary search the smallest cap that needs at most k parts.