Problem and baseline
Definition 2.4.1
(Strictly increasing subsequence and the longest-increasing-subsequence problem)
Let be a finite sequence whose values belong to a totally ordered set. A strictly increasing subsequence chooses indices and requires ; the chosen positions need not be adjacent, and no value can appear twice. The problem asks for one such subsequence of maximum length (a witness) together with that length. For the answer is length with an empty witness.
We count value comparisons and assume each takes constant time. A direct dynamic program makes the choice of state explicit: the state must record where a subsequence ends, because only the last value constrains how it can be extended.
Theorem 2.4.2
(Quadratic dynamic program for the longest increasing subsequence)
For let be the maximum length of a strictly increasing subsequence that ends at index . Then
For the optimum length is . Saving, for each with , one index attaining the maximum, and following these saved indices backwards from an index attaining , produces a witness after reversal. The method uses comparisons and space.
Proof
(Induction over the end index)
Fix and a subsequence ending at of maximum length . If it has one element, then , and by the converse inequality below no admissible exists. Otherwise it has a penultimate index with , and its first terms form a strictly increasing subsequence ending at , so . Conversely, for any with , appending to an optimal subsequence ending at is valid and has length , so . Together these give the recurrence by induction over ; the term covers the case where no admissible exists.
Every strictly increasing subsequence ends somewhere, so the optimum is . Following the saved predecessor of an index with reaches an index whose -value is exactly one smaller, so after steps the chain reaches an index with ; reversing the collected indices gives increasing indices with strictly increasing values. There are at most pairs to compare, and the arrays and the pointers have entries.
Concept lensCombinatorial
Longest path in a graph on the positions
Draw an edge whenever and . A sequence of indices is a directed path exactly when each consecutive pair is increasing in both index and value, and by chaining the inequalities this is the same as being a strictly increasing subsequence. So the problem is a longest-path problem in this acyclic graph, and is the largest number of vertices on a path ending at . The recurrence is the usual longest-path recurrence taken in index order, and the quadratic comparison count is the cost of inspecting every possible edge. The method of the next section never builds this graph.
Quick check
(Compute for the sequence and state the optimum length.)
Apply the recurrence from left to right.
Solution · Answer
. For only qualifies, so . For again only qualifies, so . For all earlier values are smaller, and , so . The optimum length is , for example or .
Minimum tails and binary search
We can compress the information needed for the length.
Definition 2.4.3
(Minimum tail list)
Fix a prefix and let be the maximum length of a strictly increasing subsequence in it. For each , the minimum tail is the smallest possible last value of a strictly increasing subsequence of length in this prefix. Each minimum exists because the prefix is finite, and each length occurs, because a subsequence of length has prefixes of every smaller length. The minimum tail list is ; it is empty when .
Theorem 2.4.4
(Minimum-tail invariant and update rule)
Let be the minimum tail list of the prefix . Then . Let , and let be the first index with , or if there is none. The minimum tail list of is obtained by setting (a new last entry if ) and leaving every other entry unchanged. Consequently, after the whole input is processed, the length of the list equals the optimum length.
Proof
(Only one entry can change)
Strictness. A subsequence attaining has a length- prefix whose last value is smaller, so .
Which lengths can end at . Every old subsequence is still available in the longer prefix, so entries can only decrease, and a decrease needs a new subsequence, which must end at index with value . Suppose such a subsequence has length . Deleting its last term leaves a subsequence of length in the old prefix with last value below , so . Because is strictly increasing, the entries below are exactly , so , that is, . On the other hand, if then , and appending to a subsequence attaining gives a subsequence of length ending at ; if , the single term has length one. So subsequences ending at have every length up to , and none longer.
The effect on each entry. For we already have , so a new subsequence ending at cannot lower . For no new subsequence of that length exists. For the new candidate satisfies , so the entry becomes (it is unchanged when ). If , the new list has one more entry equal to , and no longer subsequence exists because the old prefix had maximum length . Induction on , starting from the empty prefix, proves the rule, and the final value of is the optimum length.
Proof X-ray
Where the update rule gets its force
The one non-obvious move is to bound the length of every new subsequence by using the single comparison . Strictness of the list is used twice: it makes the entries below a prefix of the list, so that a binary search finds the cut point , and it turns the bound into . The strictness of the problem enters through the choice of the cut point: an entry equal to is not below , so it is not extended, and replaces it instead of creating a longer subsequence. The argument closes because the three cases , and together cover every entry, and only changes.
This uses a lower bound search, the first position whose tail is at least . Equal values must not extend the length; this update replaces an equal tail. For a nondecreasing subsequence, use the first tail strictly greater than instead, and revise the invariant and comparisons accordingly; the two specifications are not interchangeable.
Counterexample mode
An upper-bound search computes the wrong length
Suppose we search for the first tail strictly greater than but keep the strict specification. On the list is empty, so the first is appended: . For the second no tail is strictly greater, so it is appended again: , and the third gives . The method reports length , but a strictly increasing subsequence cannot repeat a value, and the true optimum is . The repair is the lower-bound search of the update rule: for each of the second and third , the first tail at least is , so is replaced by and the list stays , with length . The upper-bound version computes the longest nondecreasing subsequence instead.
Recovering a real subsequence
The values in need not themselves appear in input order. For input the final list is , but occurs after . To recover a witness, store , an index of an actual subsequence attaining the current , and an immutable predecessor pointer for every processed position.
Proposition 2.4.5
(Witness reconstruction with predecessor pointers)
When item is processed with cut point , set if and (a sentinel) if , and then assign . After the last item, follow the pointers from to and reverse the collected indices. For the result is a strictly increasing subsequence of length exactly , hence a witness. For return the empty sequence without looking up . The whole method uses comparisons and space.
Proof
(Pointers record chains of decreasing length)
Claim: at every moment, is the index of a strictly increasing subsequence of length ending with value , and the pointer chain from lists its indices. When item is processed, points to a subsequence whose last value is and whose last index is earlier than , so the stored predecessor is earlier than and has a strictly smaller value. Pointers stored earlier are never rewritten, so the chain from is unchanged when is set to ; the chain from has one more index than the chain from , namely in total. Induction over the processed items proves the claim, and the final chain from has indices, increasing in position and strictly increasing in value after reversal.
Binary search uses comparisons per item, giving in total. The arrays , and have entries. These bounds assume constant-time comparisons and index operations.
Counterexample mode
The tail list is not a witness
Claim: the final tail list is itself a longest increasing subsequence. For the input the lists are , and , so the final list is , of the correct length . But in the input the value occurs after , so is not a subsequence; the only strictly increasing subsequences of length two are . The stored indices show the same failure, since index is not smaller than index . The repair is the saved pointer: item (value ) stored , and following it from gives indices and the witness .
Worked examples
Worked example 2.4.6
(Minimum tails and a witness on a seven-term input)
Process . The successive minimum-tail lists are
The final length is . The saved pointers for the final entry trace values , so one witness is at indices . The tail list happens to form a subsequence here; as the preceding counterexample shows, that is not a general guarantee.
Worked example 2.4.7
(The quadratic table on four values)
For compute from left to right. . For no earlier value is smaller, so . For only qualifies, so with predecessor . For again only qualifies, so with predecessor . The optimum is . Following the pointer of index gives indices and the witness ; following that of index gives at indices . Both are maximum, which shows that the witness is not unique.
Worked example 2.4.8
(Boundary cases: empty input and repeated values)
For the list stays empty, the length is , and the witness is empty without any lookup of .
For : the lists are , then , then, for the second , the first tail at least is , so is replaced by the equal value and the list stays while becomes index . For the value no tail is at least , so and the list is with . The pointers give the chain , so the witness has indices and values . The repeated was used once only, and the length is .
Common mistakes
Common mistake
(Answering with the last state instead of the largest state)
The state describes subsequences that end exactly at , so the answer is , not . For the states are , because nothing before the is smaller. The last state is , but the optimum is , attained at index .
Common mistake
(Reading predecessors from the array of tail indices at the end)
The entries with may be overwritten by later items, so the final array is not a chain of positions. For the processing gives , , and finally . The indices are not in increasing order. The predecessor of item was saved as at the moment item was processed, and the chain gives the correct witness . Always save when item is processed.
Exercises
Quick check
(Apply the strict algorithm to . Give its length and compare it with the longest nondecreasing length.)
Use the lower-bound search.
Solution · Answer
Strict length is : each new replaces the first tail. Nondecreasing length is because all three equal values may be chosen in order.
Quick check
(Compute the strict minimum-tail list after each item of . Give one maximum-length witness and its indices.)
Process the items from left to right, replacing the first tail that is at least the new value.
Solution · Answer
The lists are , , , . Length is optimal; for example uses indices . The pointer method also recovers a valid witness.
Quick check
(Why is it unsafe to store only the final tail values if the required output is actual input indices? Give the shortest counterexample in this note and explain what extra information resolves it.)
Compare the tail list with the order of the input.
Solution · Answer
For , final tails are in the wrong input order. Store each tail's current ending index and a fixed predecessor pointer for each processed position; follow the final index's pointer chain rather than treating the tail list as the witness.