DSA Longest Increasing Subsequence

The problem

The longest increasing subsequence is the longest set of values that rises while keeping the original list order. A subsequence keeps the original order but may skip values.

Each value in the subsequence must be strictly larger than the one before it. Equal values cannot extend a run. The answer is the length of the longest such run.

cases = [
    ([10, 9, 2, 5, 3, 7], 3),
    ([1, 3, 6, 7, 9, 4, 10, 5, 6], 6),
    ([7, 7, 7], 1),
    ([5, 4, 3, 2], 1),
    ([], 0),
]
for nums, expected in cases:
    print("values", nums, "longest length:", expected)

The first list hides its best run late. The values 2, 5 and 7 rise in order, skipping everything between them. No four values in that list rise in order.

Intuition: grabbing the next larger value fails

The first idea starts at the first value and grabs each later value that is larger. It never looks back and never restarts. A large early value blocks everything after it.

nums = [10, 9, 2, 5, 3, 7]
kept = [nums[0]]
for value in nums[1:]:
    if value > kept[-1]:
        kept.append(value)
print("greedy run:", kept)
print("greedy length:", len(kept))
print("true longest length:", 3)

The greedy run keeps only 10. Starting later at 2 would keep 2, 5 and 7. The first idea cannot know which start is right without trying them all.

Brute force: test every subsequence

The brute force tests every subset of positions. It keeps the list order inside each subset, because a subset of positions is read left to right. It counts a subset only when its values strictly rise.

nums = [10, 9, 2, 5, 3, 7]
n = len(nums)
checked = 0
best_len = 0
best_run = []
for mask in range(2 ** n):
    checked += 1
    run = [nums[i] for i in range(n) if mask & (1 << i)]
    rising = all(run[k] < run[k + 1] for k in range(len(run) - 1))
    if rising and len(run) > best_len:
        best_len = len(run)
        best_run = run
print("subsets checked:", checked)
print("longest length:", best_len)
print("one longest run:", best_run)

Six values give 64 subsets. Each added value doubles the subset count. Ten values give 1,024 subsets, and twenty values give over a million.

The optimal solution: the best run ending at each index

The state is best[i], the length of the longest rising run that ends exactly at index i. That one sentence is the whole method.

Each index looks back at every earlier index. An earlier smaller value offers its best length plus one. The index keeps the largest offer, or 1 when no earlier value is smaller.

def lis_length(nums):
    if not nums:
        return 0
    best = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best)

cases = [
    ([10, 9, 2, 5, 3, 7], 3),
    ([1, 3, 6, 7, 9, 4, 10, 5, 6], 6),
    ([7, 7, 7], 1),
    ([5, 4, 3, 2], 1),
    ([], 0),
]
for nums, expected in cases:
    result = lis_length(nums)
    print("values", nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases match, including the empty list at length 0. Pair comparisons replace the subset explosion. The answer is the largest table entry, because the best run may end at any index.

Walkthrough: the table for [10, 9, 2, 5, 3, 7]

The walk fills the table one index at a time. Each line prints the table up to the index just processed. A parent table records which earlier index gave each best length.

nums = [10, 9, 2, 5, 3, 7]
best = [1] * len(nums)
parent = [-1] * len(nums)
for i in range(len(nums)):
    for j in range(i):
        if nums[j] < nums[i] and best[j] + 1 > best[i]:
            best[i] = best[j] + 1
            parent[i] = j
    print("after index", i, "value", nums[i], "table:", best[:i + 1])
end = best.index(max(best))
run = []
while end != -1:
    run.append(nums[end])
    end = parent[end]
run.reverse()
print("longest length:", max(best))
print("recovered run:", run)

The largest entry is 3, at the last index. The parent links walk back from 7 through 5 to 2. The recovered run is read straight off those links.

Complexity

Time is O(n squared). Each index compares against every earlier index, and the pair count is n times n minus 1, divided by 2.

Space is O(n). The best table and the parent table each hold one entry per value.

def count_comparisons(n):
    nums = list(range(n))
    best = [1] * n
    comparisons = 0
    for i in range(n):
        for j in range(i):
            comparisons += 1
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return comparisons

for n in [5, 10, 20]:
    print("values", n, "- comparisons:", count_comparisons(n))

Doubling the list roughly quadruples the comparisons. That growth is the price of checking every pair. It is still far below the doubling subset count of the brute force.

Edge cases and pitfalls

An empty list has no run at all, so its length is 0. A falling list and a list of equal values both answer 1, from any single value.

def lis_length(nums):
    if not nums:
        return 0
    best = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best)

print("empty list:", lis_length([]))
print("one value:", lis_length([4]))
print("falling list:", lis_length([5, 4, 3, 2]))
print("already rising:", lis_length([1, 2, 3, 4]))
print("equal values:", lis_length([7, 7, 7]))

The classic mistake lets an equal value extend a run. Swapping the strict comparison for a loose one invents runs that the problem forbids.

def lis_loose(nums):
    best = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] <= nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best)

print("loose count for [7, 7, 7]:", lis_loose([7, 7, 7]))
print("strict count for [7, 7, 7]:", 1)

Strictly larger is the whole rule, and the comparison sign carries it. A faster patience-based method for this problem exists, and it belongs to a later course.