Identifying the running-suffix DP pattern
The running-suffix DP pattern solves problems where the input is a single sequence and the answer is the best contiguous segment sitting anywhere inside it. These are generally easy or medium problems where we walk the sequence once, at each position we work out the best segment that ends right there, and the best of those values across all positions is the answer.
When a problem statement, or its natural recursive solution, fits the template below, it is a running-suffix DP problem.
Given a sequence of length
n, compute dp(i) which is the optimum over segments that end at position i, from the single earlier state dp(i-1) (extend) or the empty state's value, the identity of ⊕ (restart), combined with some function f (for example max). The answer is the best of dp(0), dp(1), .., dp(n-1).How to identify the running-suffix DP pattern
There are two signals that tell us a problem fits the running-suffix DP pattern.
A best contiguous segment, anywhere
If the input is a single array or string, and the goal is one number, the optimum over contiguous runs, the problem is generally a running-suffix DP problem. A run can be a subarray, a substring, or a streak, and it may begin and end at any position. Words like contiguous, subarray, consecutive, or streak point to this signal.
A single sequence reduces to one answer about the best contiguous run inside it.
Liking the course? Check our discounted plans to continue learning.