使用动态规划求最长递增子序列

1. Introduction

In this tutorial, we’re going to walk through the Longest Increasing Subsequence (LIS) problem.

2. Problem Statement

Given an array of unsorted elements, the idea is to find the length of the longest subsequence whose elements are in ascending order (from lowest to highest).

The elements in the subsequence do not necessarily have to appear in consecutive positions in the initial array, and the solution of LIS is not always unique.

2.1. Example

For elements {-3, 10, 5, 12, 15} we identify the following increasing subsequences.

• -3, 10, 12, 15
• -3, 5, 12, 15
• 10, 12, 15
• 5, 12, 15
• 12, 15

As we can see from the list, the longest increasing subsequence is {-3, 5, 12, 15} with length 4. However, it’s not the only solution, as {-3, 10, 12, 15} is also the longest increasing subsequence with equal length.

3. Naive Implementation

The naive implementation of LIS is to first consider all possible subsequences of the given array. Then, we check every subsequence that is increasing and store the length of it. After doing this process, we can return the length of the longest one that we found:

algorithm NaiveLIS(array):
    // INPUT
    //    array = The input array
    // OUTPUT
    //    LIS = The longest increasing subsequence
    while true:
        Sub <- all possible subsequences of array
        maxLis <- 1
        for S in Sub:
            if isIncreasing(S):
                len <- length(S)
                maxLis <- max(maxLis, len)
        return maxLis

The complexity of this approach is O(2^n) because an array of size n contains 2^n subsets. For example [1,2,3] contains subsets {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

4. Dynamic Programming Implementation

We can improve our performance with a dynamic programming approach. Recall that dynamic programming is a technique that involves breaking down a problem into multiple smaller subproblems and using those solutions to construct our larger one.

Specifically in this case, we can use tabulation:

1. Initially, we assume that every index i of an array arr[] has a LIS of one.
2. Parsing the array from left to right we look at each element at index i.
3. For every element j up until i (where j<i), if the element at index i is greater than the element at index j and lis[i] <= lis[j] then lis[i] = lis[j] + 1
4. We pick the maximum all of all LIS values

The intuition behind this algorithm is that we can find all the increasing subsequences for a number at index i by looking at all the previous numbers until i-1, eventually reaching the longest one:

algorithm DPLIS(array):
    // INPUT
    //    array = The input array of size n
    // OUTPUT
    //    LIS = The longest increasing subsequence
    n <- size of array
    Lis <- array of 1s of size n
    for i <- 2 to n:
        for j <- 1 to i - 1:
            if array[i] > array[j] and Lis[i] <= Lis[j]:
                Lis[i] <- Lis[j] + 1
    return max(Lis[0], Lis[1], ..., Lis[n])

The complexity of this is O(n^2) because we traverse the array once in the outer loop, yielding a complexity of O(n), and then for every element i, we make a linear search of all elements j from 1 up to i.

5. Conclusion

In this tutorial, we presented the Longest Increasing Subsequence problem.

We also had a look at a naive implementation and one using dynamic programming.