Where it runs
1. The problem
You compare two versions of a file and want the diff to show what stayed the same. Lines were added, removed and moved around. The unchanged part is the longest set of lines found in both files in the same order, even when other lines sit between them. That is what git diff works out every day.
A related task. You get build numbers in a random order. Find the longest chain of upgrades you could apply following this list without ever going back to an older build.
Both questions have one shape: pick the longest part you can keep in order. You may skip the items between the ones you pick.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedlongestIncreasingSubsequence([2, 5, 3, 7, 4, 8])Find the longest subsequence that keeps rising. Every dp[i] starts at 1, because arr[i] alone is a chain of length 1.
Bars: the input numbers, never moved. A lit bar is a number being read; picking a subset lights up all its members.
One operation is one element read, or picking the next subset. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(2ⁿ·n)O(n²)O(n log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- longest increasing subsequence
- longest common subsequence between two strings
- minimum edits to turn one string into another
- keep relative order, may skip items
- diff or alignment between two sequences
Looks similar, isn't
- Dynamic programming (1-D)
One index is enough there. Comparing two sequences needs two of them.
- DP on strings (word break)
That page splits a single string into pieces. This one lines two sequences up.
- Binary search (array)
The n log n form of increasing subsequence uses binary search. The table form is the slower one.
- Two pointers (same direction)
Checking whether one string is a subsequence needs no table. Finding the longest common one does.
One sequence of n items costs O(n²) time. Two sequences of n and m cost O(nm), and one kept row is enough.
On LeetCode
Problems that pick items in order, gaps allowed, so that each pick grows, divides or chains with the one before. For each position keep the best answer that ends there by checking every earlier position, O(n^2).
The lesson's lengthOfLIS. n is at most 2500, so the O(n^2) table passes.
Next to each length keep how many picks reach it, and add the counts when two earlier spots give the same length.
Sort the numbers first, then run the lesson's loop with "divides" in place of "is smaller", and keep a link to the previous item to rebuild the set.
Build the increasing table from the left and again from the right. The best peak keeps the most items, and it needs at least one item on each side.