CSES - DP Function Shape

$dp[i]$ as a function of $v$ (the value of $a_i$) is convex and piecewise linear. Initially, $dp[0](v) = |v - a_0|$, a V-shape centered at $a_0$.

Adding $|v - a_i|$ keeps convexity. The constraint "$v \geq \text{previous value}$" truncates the function on the left, preserving only the non-decreasing part. The minimum of $dp[i]$ is at the largest breakpoint less than or equal to the current choice. A max-heap tracks these breakpoints.