Algorithm: Longest Increasing Subsequence Problem

Problem Description#

Given an integer sequence of length $n$ , $A=[a_1, ..., a_n]$ , find a subsequence (not necessarily contiguous) such that its elements are strictly increasing and its length is the longest. Sometimes, it is also required to reconstruct this longest subsequence.

Example:

A = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 101]  # Length is 4

Application Scenarios#

Analysis of DNA sequence structures in bioinformatics
Finding upward trends in stock analysis
Optimal control of sequences in robot path planning

Solution 1: Dynamic Programming#

Idea: Define $dp[i]$ as the length of the longest increasing subsequence ending with the $i$ -th element, with initial values all set to 1.
State Transition Equation: $dp[i] = max(dp[j] + 1) \quad \forall j < i ~~\& ~~A[j] < A[i]$

def LIS_DP(A):
    n = len(A)
    dp = [1] * n

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

    return max(dp)

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$

Can return the LIS sequence.

Solution 2: Greedy + Binary Search#

Idea: Maintain an array tail, representing the smallest ending element of all increasing subsequences of length k.
For each number x, we find the first position i in tail that is greater than or equal to x.
If found, replace $tail[i]$ with x (greedy, because a smaller ending is more likely to extend a longer increasing subsequence).
If not found (indicating x is larger than all), append x to the end of tail.
Finally, len(tail) is the length of the longest increasing subsequence.

Example Explanation

A = [10, 9, 2, 5, 3, 7, 101, 18]

tail = []

# Changes in tail
10    → [10]
9     → [9]
2     → [2]
5     → [2, 5]
3     → [2, 3]
7     → [2, 3, 7]
101   → [2, 3, 7, 101]
18    → [2, 3, 7, 18]

# Conclusion: LIS length is 4

Pseudocode:

import bisect

def LIS_binary_search(A):
    tail = []
    for x in A:
        i = bisect.bisect_left(tail, x)
        if i == len(tail):
            tail.append(x)
        else:
            tail[i] = x
    return len(tail)

Why can't we directly use tail to get the LIS sequence?

Because tail is not the LIS itself; it is a "greedy compression of multiple potential LIS," which is continuously overwritten and replaced, not retaining the complete path.

For example:

A = [3, 10, 2, 1, 20]
# tail could be: [1, 10, 20]
# But LIS is [3, 10, 20]

Use DP + Backtracking to Recover the LIS Sequence#

Idea: To output the LIS itself, we need to additionally record "the predecessor of each position."

dp[i]: Represents the length of the longest LIS ending with A[i].
pre[i]: Represents the index of the previous element before A[i] (used for backtracking the path).
Traverse each position i, find all j < i such that A[j] < A[i] in dp[j], then:
If dp[j] + 1 > dp[i], update dp[i] = dp[j] + 1 and set pre[i] = j.

def get_LIS_sequence(A):
    n = len(A)
    dp = [1] * n
    pre = [-1] * n  # For backtracking the path

    max_len = 1
    last_index = 0

    for i in range(n):
        for j in range(i):
            if A[j] < A[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                pre[i] = j

        if dp[i] > max_len:
            max_len = dp[i]
            last_index = i

    # Backtrack the path
    lis = []
    i = last_index
    while i != -1:
        lis.append(A[i])
        i = pre[i]

    lis.reverse()
    return lis

Exercise#

Luogu B3637 Longest Increasing Subsequence