Longest Increasing Subsequence (LIS)

#How does it work?

The longest increasing subsequence (LIS) is the longest strictly increasing sequence you can get by deleting some elements of a sequence of numbers. For [3, 10, 2, 1, 20, 4, 6, 7] the answer is [3, 4, 6, 7] (length 4).

dp[i] is the length of the longest increasing subsequence that ends at a[i]. For every earlier a[j] smaller than a[i], a[i] can extend the sequence ending at j: dp[i] = 1 + max(dp[j]). If there is none, dp[i] = 1.

prev[i] remembers which j was extended; following prev[] back from the largest dp value recovers the subsequence. There is also a faster method: keep the smallest ending value for each length and use binary search to get O(n log n).

#Try it yourself

#Step by step

1. 01Start with dp[i] = 1 for every i.
2. 02For each i, look at every earlier j: if a[j] < a[i] and dp[j] + 1 > dp[i], set dp[i] = dp[j] + 1 and prev[i] = j.
3. 03The answer is the largest value in dp.
4. 04Read the subsequence backwards by following prev[] from that position.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def lis(a: list) -> list:
    n = len(a)
    dp = [1] * n        # dp[i] = longest increasing subsequence ending at a[i]
    prev = [-1] * n     # the element before a[i] in that subsequence
    for i in range(1, n):
        for j in range(i):
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    i = dp.index(max(dp))
    out = []
    while i != -1:
        out.append(a[i])
        i = prev[i]
    return out[::-1]


result = lis([3, 10, 2, 1, 20, 4, 6, 7])
print(len(result))
print(" ".join(map(str, result)))

#Complexity

Every i looks at all earlier j, so it is O(n²). Keeping tails[k] = the smallest last element of an increasing sequence of length k + 1, each number is placed with binary search, bringing it down to O(n log n).

#When to use it?

The longest upward trend in a time series, box-nesting (Russian doll) problems, the longest consistent order in version or change logs, and the patience sorting card game all build on LIS.

#Practice

Log in to answer questions and save your progress.