Longest Increasing Subsequence

Longest strictly increasing chain within a sequence. dp[i] = the best chain ending at position i, extending any smaller earlier element.

Category

Dynamic Programming

Time complexity

O(n²)

Space complexity

O(n)

Pseudocode

dp[i] ← 1
extend any smaller earlier value
dp[i] = max(dp[j]+1) for a[j]<a[i]
answer = max(dp)

Reference implementation

for i in range(n):
    dp[i] = 1 + max((dp[j]
        for j in range(i)
        if a[j] < a[i]), default=0)

Open the interactive Longest Increasing Subsequence visualisation →