Two algorithms find the same length. The quadratic table stores, for each position, the longest increasing run ending there, and a predecessor, so the run itself can be read back. The binary-search method keeps the smallest possible last value for each length and finds the same number far faster — and what it holds at the end is not a subsequence of the input, though on the sequence in front of you it happens to be one.
Core ideas
The hard idea is the invariant the tails array maintains, which is about lengths and not about any particular run, and which is why its contents need not be a run at all.
best(i) is the length of the longest increasing subsequence ending exactly at position i. It is one more than the largest best(j) over earlier positions holding smaller values, and recording which j attained that maximum makes the subsequence recoverable. The whole array takes Θ(n²) comparisons — 45 on ten values — and the answer is the largest entry.
tails(L) is the smallest value that can end an increasing subsequence of length L among the elements seen so far. Each new value replaces the first entry that is at least as large, or extends the array. The invariant is about what is achievable at each length; nothing says the entries occur in the input in that order, and usually they do not.
An answer must be increasing and must be a subsequence of the input. The tails array is always increasing — that is forced by the invariant — so checking only that property will never catch it. On the lab's default sequence it also happens to be a subsequence, which is worse: the check passes and the array still is not the answer the table found. Switch to the sequence with repeats and the subsequence check fails outright.
The material
The quadratic table, the binary-search invariant, the two checks, and the instance where agreement is a coincidence.
A subsequence of a sequence is what is left after deleting zero or more entries, keeping the rest in order. It is strictly increasing if each entry is larger than the one before. The problem is to find a longest strictly increasing subsequence; there may be many, and the lesson is careful never to call one of them the answer.
Let best(i) be the length of the longest strictly increasing subsequence ending at position i. Then best(i) = 1 if no earlier position holds a smaller value, and otherwise best(i) = 1 + max of best(j) over positions j < i with a(j) < a(i). The answer is the maximum over all i.
A longest increasing subsequence ending at i has some second-to-last entry, at a position j < i with a(j) < a(i), unless it consists of a(i) alone. Removing a(i) leaves an increasing subsequence ending at j, and it must be a longest one, or substituting a longer one and re-appending a(i) would beat the original.
So the length is 1 + best(j) for that j, and taking the maximum over all admissible j gives best(i). Every increasing subsequence ends somewhere, so the overall answer is the largest best(i), and the predecessor recorded at each step reconstructs one witness for it.
□
The binary-search method processes the values in order and keeps an array tails in which position L holds the smallest value that ends an increasing subsequence of length L + 1 among the values processed so far. A new value either extends the array, when it is larger than everything in it, or replaces the first entry that is at least as large. Both cases are found by binary search, so the whole run is Θ(n log n) comparisons — 14 on ten values, against the table's 45.
Nothing in that description promises the array is a subsequence of the input. It is a record of what is achievable at each length, and its entries may come from positions in any order, including positions that cannot coexist in one run. The length is right, because the array's length is exactly the longest achievable, and the contents are a different question.
On 10 9 2 5 3 7 101 18 4 8 the tails array after the seventh value is 2 3 7 101, which is a genuine longest increasing subsequence. Then 18 replaces 101, then 4 replaces 7, then 8 replaces 18, and the array ends as 2 3 4 8. The table's reconstruction is 2 5 7 101. Both have length 4 and both are valid answers here; the array passed through one valid answer on its way to a different one, and nothing about the mechanism guarantees the destination is valid.
That last sentence is the whole lesson, and the lab has the instance that proves it. Switch the sequence to 3 1 4 1 5 9 2 6 5 3. The tails array ends 1 2 3 6, which is increasing; the panel's second check asks whether it is a subsequence of the input, and the answer is no — 1, 2 and 3 occur in that order, and the only 6 sits before the last 3. The table's reconstruction is 3 4 5 9, which passes both checks.
The panel reports is increasing and is a subsequence of the input as separate verdicts. The first is satisfied by the tails array on every input, because the invariant forces it, and by a sorted copy of the input too — which is why it cannot be the only check. The second is the one with teeth. A reconstruction that returns the right values in the wrong positions fails it, and so does an array that was never a run in the first place.
The third route is the enumeration: every one of the 2ⁿ subsequences, tested for increase, with the longest kept. On ten values that is 1 024 subsets, which is instant, and the lab refuses above sixteen values. It agrees with both algorithms on the length, which is what makes the comparison of the two arrays a comparison rather than a guess.
The measured comparison counts are 45 and 14 on ten values. The proved bounds are Θ(n²) and Θ(n log n), and the enumeration is Θ(2ⁿ n). Here the three measured numbers and the three bounds agree in order, which is worth saying out loud on a course where three pages show them disagreeing. What does not follow from the measurement is the shape of either curve: 45 and 14 are two numbers, and two numbers fit any pair of curves you like.
Interactive
Three routes to the length, and two separate checks on the subsequence
Method
Agreement on a number is the weakest kind of agreement, and it is the one that is easiest to mistake for correctness.
The table's array holds an answer per position; the tails array holds a bound per length. Those are different objects with the same shape, and the shape is what invites the confusion. Write the sentence defining each entry before comparing them.
The subsequence comes out of the table's recorded predecessors. If you need the run itself and you are using the binary-search method, you must record predecessors there too — the tails array alone cannot produce it.
Increasing, and a subsequence of the input. The first is satisfied by things that are not answers at all, including a sorted copy of the input, so a check that stops there has not tested anything the failure mode can fail.
On the lab's default the tails array is a valid answer, and on the sequence with repeats it is not even a subsequence. If an invariant does not promise a property, a single input exhibiting the property is a coincidence to be checked against a second input, not evidence.
Forty-five and fourteen at one length. The bounds Θ(n²) and Θ(n log n) come from the structure of the loops, and no pair of measurements establishes them.
Each line is one value being processed. Position is where the binary search placed it: past the end extends the array, anywhere else replaces an entry. The input is 10 9 2 5 3 7 101 18 4 8.
Only the length is shared. The table's run is 2 5 7 101, occupying positions 3, 4, 6 and 7 of the input; the tails array is 2 3 4 8, whose values occur at positions 3, 5, 9 and 10 and which is also a valid run here. Two valid answers and one number, and the panel says whether the two coincided rather than assuming they must.
Watch the seventh line. At that moment the tails array is 2 3 7 101, a perfectly good answer, and the algorithm then overwrites it three times because smaller endings become available. Each of those replacements is correct for the invariant it maintains — the smallest possible last value for each length — and each of them destroys a run that was there a moment ago. The array is doing its job; its job is not to hold a run.
For a faded rehearsal, switch the sequence to 3 1 4 1 5 9 2 6 5 3 before running it. The supplied first move: the value 1 appears twice and equal values cannot both sit in a strictly increasing run, so the second 1 replaces rather than extends. Predict the final tails array, then check the panel's second verdict — this is the instance where the array is not a subsequence at all.
You should be able to state the per-position recurrence and the tails invariant in one sentence each, recover a run from predecessors, check a candidate for both required properties, and produce the input on which the faster method's array is not an answer.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.