What does a small ending value buy us?
Definition 14.2.1
(Strictly increasing subsequence)
A subsequence of keeps elements in their original order but may skip some; it is determined by indices . It is strictly increasing when , so each chosen value is smaller than the next.
For example, is a subsequence of , while is not: the 6 appeared before the 2 and 4.
For two increasing subsequences of the same length, the one with the smaller final value is at least as easy to extend with a future value. This does not mean its earlier elements are the same, or that one chosen set of tails is itself a subsequence. The useful state is an optimum ending value for each length separately.
Definition 14.2.2
(Minimum tail of each length)
For an integer input , let be the smallest possible final value of a strictly increasing subsequence of length in the processed prefix. Store in an array tails at indices , where is the largest attainable length. An empty prefix has an empty array.
The tails are strictly increasing
Theorem 14.2.3
(Minimum tails increase strictly)
For every processed prefix, .
Proof
(Compare a best longer subsequence with its shorter prefix)
For , choose a length- subsequence ending at . Its first selected elements form a length- subsequence whose last value is strictly less than . Because is the smallest attainable ending value of length ,
Thus tails is strictly increasing. Each minimum exists because a finite prefix has only finitely many subsequences.
This order allows a binary search. On reading a new value , find the first position j where tails[j] >= x, or take j = len(tails) if there is none. Replace that tail by , or append at the end.
Theorem 14.2.4
(One minimum tail changes per item)
Let j be the first position with tails[j] >= x, or len(tails) if there is none. After reading , the minimum tail of length j+1 becomes (it is replaced, or created at the end), and the minimum tail of every other length is unchanged.
Proof
(Only the length j plus one state can improve)
Before reading , every tail before j is less than . If j>0, a length-j subsequence ending at tails[j-1] can therefore be extended by . For j=0, alone supplies length one. So a length-j+1 subsequence ending at exists.
For any shorter length, the previous minimum tail is already less than , so ending at cannot improve it. For a length greater than j+1, an increasing subsequence ending at would need an earlier subsequence of length at least j+1 ending below . If j is within the old array, its minimum tail is already at least , a contradiction. If j is at the end, no old longer subsequence exists. Thus only the length-j+1 state can improve or be created. Replacing or appending preserves all the minimum-tail meanings.
Proof X-ray
Where strictness and sortedness are used
Two earlier facts carry this proof. Strict monotonicity of the tails makes the binary search valid and gives the claim that all tails before j are below while tails[j] is not. The non-routine move is the last step: a subsequence of length greater than j+1 ending at would contain a length-(j+1) prefix ending strictly below , which tails[j] >= x forbids, so no longer state can change. The first-at-least rule is exactly what strictness needs: a tail equal to cannot be extended by , so it must be replaced, not skipped. With a first-strictly-greater rule the proof would break at "ending at is possible after every shorter tail".
Use the first tail at least , not the first strictly greater tail. Equality cannot extend a strictly increasing subsequence. For input , the tail array remains and the answer is one. A nondecreasing-subsequence problem has a different condition and uses the first tail strictly greater than .
Concept lensCombinatorial
The tails as the tops of piles
Deal each item onto the leftmost pile whose top is at least , opening a new pile if there is none. Every pile is then non-increasing, and the pile tops are exactly tails. For the piles are , , . Two items of an increasing subsequence never share a pile, so piles certify that no increasing subsequence is longer than .
Common mistake
(Using the first strictly greater tail for a strict chain)
With bisect_right in place of bisect_left, the input gives bisect_right([2],2)=1, so is appended again and the tails become , then . The reported length is wrong: no two equal values form a strictly increasing subsequence, so the correct length is .
A tail array is not necessarily a subsequence
Counterexample mode
Minimum tails can come from incompatible witnesses
Process . The arrays are
The final values are increasing, but their source indices are in zero-based indexing. They are not a subsequence of the input. The entry 6 witnesses a length-three subsequence ; the later replacements for shorter lengths are independent optima.
The array length still gives the correct maximum length. To return actual indices, record which earlier witness a new item extends at the moment it is processed.
Preserve a witness when a tail is replaced
Keep end[j], the input index of a witness attaining tails[j], and prev[i], the predecessor index chosen for item . When is placed at position j>0, set prev[i] = end[j-1] before replacing any tail or end index. For j=0, its predecessor is absent. Then set end[j]=i, appending if necessary.
Theorem 14.2.5
(Recorded predecessor links give an optimal witness)
Let end[j] and prev be maintained as above. After every item, end[j] is the last index of a real strictly increasing subsequence of length j+1 with final value tails[j]. Following prev from end[L-1] and reversing yields a strictly increasing subsequence of the maximum length .
Proof
(Predecessor links remain valid after later replacements)
Induct over the input positions. Every end[j] names the last element of a real length-j+1 increasing subsequence in the processed prefix with final value tails[j]. For a new position j>0, the existing witness at end[j-1] occurs earlier and ends at a value strictly less than . Appending the current item yields a valid witness of length j+1; the j=0 case is a one-element witness.
The new prev[i] stores a fixed input index, not a pointer to a mutable tail slot. Later replacements may change end[j-1], but cannot alter that previously recorded predecessor. Following links from the final end[L-1] therefore yields earlier indices and strictly increasing values after reversal. It has length , which the tail invariant proves optimal.
from bisect import bisect_left
def longest_increasing_subsequence(a):
tails, end = [], []
prev = [-1] * len(a)
for i, x in enumerate(a):
j = bisect_left(tails, x)
if j > 0:
prev[i] = end[j - 1]
if j == len(tails):
tails.append(x)
end.append(i)
else:
tails[j] = x
end[j] = i
indices = []
current = end[-1] if end else -1
while current != -1:
indices.append(current)
current = prev[current]
indices.reverse()
return indices, [a[i] for i in indices]
Worked example 14.2.6
(Tracing the three arrays on a short input)
Run the code on and record tails, end and the new prev after each item.
| item | j | prev[i] | tails | end | |
|---|---|---|---|---|---|
| 0 | 3 | 0 | |||
| 1 | 5 | 1 | 0 | ||
| 2 | 6 | 2 | 1 | ||
| 3 | 2 | 0 | |||
| 4 | 4 | 1 | 3 |
The final end[2]=2 and prev[2]=1, prev[1]=0, so the witness indices are with values . The entry at index has predecessor index , a valid length-two chain , even though that chain is not extended to length three.
Worked example 14.2.7
(Equal values: an edge case)
For , the first item gives tails and end . For the first tail at least is at position , so the tail is replaced by , prev[1]=-1, end[0]=1, and the same happens for index . The final tails is , the length is , and the reconstruction returns indices and values . The empty input gives end empty, current=-1, and two empty lists.
Worked example 14.2.8
(A replacement that must not disturb a stored link)
Run the code on . Item : tails . Item (, j=0): tails , end . Item (, j=1): prev[2]=end[0]=1, tails , end . Item (, j=1): prev[3]=end[0]=1, and the entry is replaced: tails , end . Item (, j=2): prev[4]=end[1]=3, so tails and end . Following links from index gives , indices and values . The link prev[4]=3 points at the current holder of length two, not at the replaced value at index .
The input is a sequence of integers as a precondition; the function does not mutate it. It returns one optimal index sequence and its values, not necessarily the lexicographically smallest optimum. Empty input returns two empty lists. For , the final length-three endpoint is still index 2, so following its recorded links returns indices and values .
Count the work and the output
Proposition 14.2.9
(Cost of the tail search)
For items, the implementation performs comparisons and stores entries; reconstructing a witness of length takes time.
Proof
(Binary searches and stored arrays)
Each of the items performs one binary search in an array of at most entries, which takes comparisons, plus a constant number of assignments. The arrays tails, end, prev and the returned index list each have at most entries. Reconstruction follows links, one per step, then reverses a list of length .
These are entry and comparison bounds; the bit costs of arbitrary-sized integer comparisons are separate. Computing only the length can omit the predecessor array, but returning a witness requires additional information and a correctness argument.
The method does not count how many optimum subsequences exist, nor does it solve a variant with weights or gaps without changing its state and proof. The words “strictly increasing” determine the binary-search comparison and the witness condition.
Common mistake
(Expecting one particular optimum)
For both and have the optimal length three. The code replaces the length-two tail by and returns indices , that is . The algorithm certifies a longest chain, not the lexicographically smallest or the earliest one.
Exercises with solutions
Quick check
(Process . What is the strict answer, and what would a nondecreasing version permit?)
Track the tail array after each item.
Solution · Answer
tails stays , so the strict length is 1. All three values form a nondecreasing subsequence of length 3; its update must use the first tail greater than .
Quick check
(Why is not a valid witness for ?)
Look at the input positions of the three values.
Solution · Answer
Their source indices are , which are not increasing. The separately optimal tails need not come from one chronological chain.
Quick check
(For , give an optimal witness and explain why it survives later tail changes.)
Which links were stored when and were processed?
Solution · Answer
Indices give . The predecessor links stored when 5 and 6 were processed remain unchanged when later items replace the length-one and length-two endpoints.
Quick check
(Why is bisect_left used for strict increase?)
What should happen when equals an existing tail?
Solution · Answer
It replaces the first tail equal to , rather than appending an equal value. A strictly increasing chain may only extend a tail smaller than .
Quick check
(Give tails after processing and the length it reports.)
Each item is no larger than the existing tail.
Solution · Answer
After : . For the first tail at least is at position , so ; for , . The reported length is , correct because no two values are increasing.
The proof has two layers: minimum tails certify the optimum length, and immutable predecessor indices certify a real subsequence attaining it.