Understanding the running-suffix DP pattern

A large family of problems asks us for the best contiguous stretch of a sequence. Finding the most profitable run of trading days, the warmest unbroken spell of weather, or the strongest streak of sensor readings are all problems of this kind. The best stretch can sit anywhere in the sequence and can have any length, and so, we have to consider every possible ending point and keep the best of them.

Problems like these are solved by the running-suffix DP technique, where we compute for each position the best stretch that ends exactly there, and then take the best of those answers across the whole sequence. Each ending-point answer is built in one step from the previous ending-point answer, so the whole computation moves along the sequence in a single pass.

The running-suffix DP pattern is a classification of problems that can be solved using the running-suffix DP technique.

Note that a sequence here can be an array or a string, anything indexed by a position 0, 1, ..., n-1. From here on we will use an array as our example, but everything applies to strings as well.

The subproblems of running-suffix DP form a 1D array dp[0..n-1]

In this lesson we will learn the running-suffix DP technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.

The running-suffix DP technique

Every running-suffix DP problem is an instantiation of the Bellman optimality equation, built from a state together with its three components, the action set, the cost function, and the transition function. Everything else, the recurrence, the dependency order, and the target, follows from them.