Longest rising sequence of picks from a list

Dynamic programming Senior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

from bisect import bisect_left
tails: list[int] = []
for v in [10, 9, 2, 5, 3, 7, 101, 18]:
    k = bisect_left(tails, v)
    if k == len(tails):
        tails.append(v)
    else:
        tails[k] = v
print(len(tails), tails)

Options4 [2, 3, 7, 18]4 [2, 5, 7, 101]3 [2, 3, 7]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 4 [2, 3, 7, 18]

Right: length 4 (for example 2, 3, 7, 18), and tails holds the smallest ending of each length.

Keeping the smallest tail for each length leaves the most room for later values, which is why replacing is safe.

Why not the others?

B 4 [2, 5, 7, 101]. Later values replace 5 with 3 and 101 with 18.
C 3 [2, 3, 7]. 101 and then 18 extend it to length 4.

30-second answer

The O(n²) DP sets best[i] = 1 + the largest best[j] for j < i with a smaller value. The faster method keeps tails[k] = the smallest possible last value of a rising pick of length k + 1. For each value, binary search the first tail that is not smaller and replace it, or append if none. The length of tails is the answer: O(n log n) time, with O(n) space for tails.

Practise saying it · 60 s. No recording, just a timer

Explain the longest rising picks.

Say your answer out loud, then check which of these points you covered:

best[i] in O(n²)
Tails + binary search
O(n log n)

Deep dive

This is the 'longest increasing subsequence' pattern; the tails list is not itself a valid answer, only its length is.

bisect_left gives strictly rising; bisect_right allows equal values.

Keeping parent links lets you rebuild an actual sequence.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

from bisect import bisect_left


def longest_rising(values: list[int]) -> int:
    tails: list[int] = []  # tails[k]: smallest end of a rise of k + 1
    for v in values:
        k = bisect_left(tails, v)
        if k == len(tails):
            tails.append(v)  # v extends the longest rise
        else:
            tails[k] = v  # v is a smaller end for that length
    return len(tails)

Common mistakes

Thinking tails holds a real sequence.
Using bisect_right when the rule is strictly bigger.

Senior take & follow-ups

Offer the O(n²) version first, then the tails trick as the improvement.

Follow-up questions

Think of your answer first, then open the hint.

How do you rebuild one longest sequence?
Show hint
Store, for each value, the index of the tail before it when it was placed, then walk back.
Where does this appear in practice?
Show hint
Ordering boxes that nest, scheduling with deadlines and diff tools that minimise moves.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.