##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Convex function
as a function of the -th value is convex and piecewise linear. Initially, , a V-shape centered at . Adding preserves convexity. The constraint "" truncates the function on the left, keeping only where is at least the previous minimum.
After each step, the minimum of is at some breakpoint. You track breakpoints with a max-heap. The heap top is the best last value.
