LIS and state machines

How do you carry the right few states forward?

About 80 minutes · open lesson · Coding

The best-you-could-have-done line

A savings app lets people buy and sell digital gold at one price per day, and the yearly statement is getting a new line: the most profit you could have made this year with hindsight. One rule makes it hard. After a sale the money settles the next day, so you cannot buy again until the day after.

The direct approach lists plans. Every day you buy, sell or wait, so the script lists every valid plan and keeps the best one. On 30 days of prices it finds 26,931,732 plans and takes most of a minute. Count the plans for a year before reading on: the number has 90 digits, so listing them is impossible.

So ask what tomorrow needs to know about the past. Tomorrow does not care which day you bought on, or what you did in March. It cares only whether you are holding gold, whether you sold today, or whether you are free to buy. And for each of those three situations, it needs only the best profit that any plan has reached so far.

Pause and predict How many numbers does each day need to carry to the next?

Keep only the states that can still matter

Both halves of this unit are 1D DP with one change: instead of keeping one cell for each index, you keep one value for each situation the problem can be in. The question to ask is always the same: which few facts about the past does the future need?

Longest increasing subsequence

Given nums, find the longest subsequence whose values strictly increase. The 1D DP method from Unit 18 works directly. There is also a faster method that keeps different facts about the past.

Pause and predict You have two increasing subsequences of the same length. One ends at 8, and the other ends at 3. Which one can you safely forget?

tails is sorted. Take the increasing subsequence of length k + 2 with the smallest end, and drop its last element. What is left is an increasing subsequence of length k + 1 that ends at a smaller value. So tails[k] < tails[k + 1], and a binary search works on tails.

A new value x changes exactly one entry. Let i be the lower bound, the position of the first tail ≥ x. Every length up to i has a subsequence ending below x, so x can extend one of length i into one of length i + 1. No subsequence of length i + 1 or more ends below x, so x cannot make anything longer than i + 1. And x ≤ tails[i], so x is the new smallest end for length i + 1. If i is past the end of tails, x creates the new length i + 1.

Replacing an entry never loses an answer. This is an exchange argument. The subsequence that ended at the old tails[i] still exists. But every later value that could extend it is above the old tail, so it is also above x, and it can extend the new subsequence too. Swapping in the smaller end value removes no future possibility.

One consequence: tails is not itself a subsequence of nums. Each entry is the smallest end for its own length, and different entries can come from different subsequences. The worked example below ends with tails = [1, 2, 5], but in nums the 5 comes before the 2. Only the length of tails is the answer.

Whether the subsequence must be strictly increasing changes one character of the code. "Strictly increasing" uses the lower bound, so a value equal to an existing tail replaces it and never extends past it. "Never decreasing" uses the upper bound (the first tail > x), so an equal value goes after it. On [5, 5, 5], the first gives 1 and the second gives 3.

Two dimensions: sort one, LIS the other

One envelope fits inside another when both its width and its height are strictly smaller. If you sort the envelopes by width, a chain of nested envelopes becomes an increasing subsequence of heights. But two envelopes with equal widths never nest, and that needs care.

Pause and predict Envelopes [2, 3], [2, 4], [3, 5]. Sort by width, ties by height ascending, then take the LIS of the heights. What does it say?

State machines

Stock problems look different but use the same idea. On any day, the future needs to know only your situation: whether you own a share, whether you just sold, and how many trades you have used. Name those situations, keep one number for each (the best profit of any history that ends in that situation), and move all of them forward one day at a time. This is called a state machine DP.

Here is why it is correct. Every plan ends the day in exactly one state, and it got there by one move from the state it was in yesterday. So the best profit for each state is the best over the moves that lead into it, each using yesterday's best value. States that are impossible at the start, such as holding a share before any day, start at -∞ so that a max never picks them.

Every update must read yesterday's values, as in Maximum Product Subarray, where hi and lo are both updated from the old pair. In the stock problems, getting this wrong silently removes one of the rules.

Pause and predict Run the cooldown machine on prices [2, 1, 4, 5, 2, 9, 7], but update each state in place, one line after another, so later lines read values already changed today. The right answer is 10. What does this version print?

At most k trades is the unlimited machine with a count of trades added to the state. There is one shortcut. A profitable trade needs a stretch of rising prices, and n days contain at most n / 2 separate rising stretches. So when k ≥ n / 2, the limit can never be reached, and the answer is the same as for unlimited trades: the sum of every daily rise.

How to recognise it

There are two families. Phrases such as "longest chain", "most nested" and "fewest deletions to make it increasing" point to LIS, often after a sort. A process that moves through a few situations over time, such as holding, cooling down or counting trades used, points to a state machine. Name the situations before anything else.

Pause and predict Which of these is an LIS in disguise?

Four that only look like it

A contiguous run. The longest increasing subarray takes one pass with a counter, or a sliding window. A subsequence may skip elements, so it needs this unit's methods.
Picking the most ranges that do not overlap. Sorting by end and taking ranges greedily is an intervals problem. Nesting needs both dimensions to increase, which that greedy cannot check.
Unlimited trades with no other rule. Adding up every daily rise is a correct greedy. A cooldown, a fee or a limit on trades breaks that greedy, and the state machine handles all three.
Two sequences. The longest common subsequence needs a table over two prefixes, which is DP on grids and strings.

Where it bites

Pause and predict Java: int hold = Integer.MIN_VALUE; then hold - 3. What is it?

Sorting envelopes of equal width by height ascending. Envelopes of the same width then chain by height, so [[2, 3], [2, 4], [3, 5]] answers 3 instead of 2.
Using the wrong bound. A strictly increasing subsequence needs the lower bound. The upper bound counts [5, 5, 5] as 3.
Returning tails as the subsequence. It has the right length but usually the wrong values.
Updating states in place. A state then reads another state that has already moved to today, and a cooldown or a trade limit quietly disappears.
Starting an impossible state at 0. Holding a share before day 0 is impossible, so it must start at -∞; 0 would mean you got a share for free.
Skipping the k ≥ n / 2 check on Stock IV. The answer is still correct, but you build an O(n·k) table for a limit that can never be reached.

Open the interactive lesson

The interactive lesson adds the predictions with their answers, the labs, and graded practice with spaced review.