Partition DP

Opening scenario

Problem references use LC for LeetCode.

Split nums into k non-empty contiguous subarrays so that the largest subarray sum is as small as possible. Return that minimized largest sum (LC 410, Split Array Largest Sum). The interviewer will then change the score. Maximize a sum after capping segment lengths: cap a group's length, turn each element into its group's largest value, and maximize the total. Score by average instead: split into at most k groups and maximize the sum of the group averages. Minimum cost to merge stones into one pile: each merge joins a fixed number of neighboring piles and costs their total. Repeat until one pile is left.

For Split Array Largest Sum, nums is non-empty and contains non-negative integers, with 1 ≤ k ≤ len(nums). The length-capped maximum-sum variant also uses non-negative values; the averages variant uses positive values. Start by fixing the final group and asking what must already be solved for the prefix before it.