Longest Increasing Subsequence (LIS) - Course 3

Module 1: 2D DP

Longest common subsequence (LCS)
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) in $O(N \log N)$
Knapsack problem
Lazy DP

Module 2: DSU

System of disjoint sets

Module 3: MST

Minimum and maximum spanning trees
Kruskal's Algorithm
Prim's Algorithm
Borůvka's Algorithm

Module 4: Combinatorics

Stars and columns
The principle of inclusion-exclusion

Module 5: Geometry

Finding the area of a simple polygon

Module 6: Arbitrary-Precision Arithmetic

Long Arithmetic

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Binary Heap

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 3/Module 1: 2D DP/Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence (LIS)

Longest increasing subsequence (LIS)

Problem statement

Given a sequence $a_1, a_2, \ldots, a_n$ . It is required to find its increasing subsequence of maximum length.

For example, the longest increasing subsequence of $[2, 4, 1, 4, 2$ is .

Up next

Longest Increasing Subsequence (LIS) in $O(N \log N)$

Longest Increasing Subsequence (LIS) in $O(N \log N)$

,

3

,

6

,

10

]

[2, 4, 1, 4, 2, 3, 6, 10]

[2, 4, 1, 4, 2, 3, 6, 10]

[1, 2, 3, 6, 10]

Solution

Solution 1

Create a copy of the sequence $a$ and sort it in increasing order. Let it be $b$ . Then the answer for the original problem is the LCS of sequences $a$ and $b$ .

Solution 2

Let $dp(i)$ denote the solution for the prefix of array $a$ of length $i$ under the condition that the element at position $i$ is included in the answer. I.e. the length of the longest increasing subsequence of $a[1 \ldots i]$ where $a_i$ is included in the answer.

The base case is:

dp(0)=0

Now let us try to find transitions for the general case $dp(i) \ (0 < i \leq n)$ . Let us analyze the transitions. By definition of $dp(i)$ we must include $a_i$ in the answer. I.e. the last element of the increasing subsequence of the prefix $a[1 \ldots i]$ is $a_i$ . Then we have two cases:

The increasing subsequence of the prefix $a[1 \ldots i]$ consists only of $a_i$ . Then $dp(i) = 1$ .
Otherwise, let us iterate over the penultimate element of the increasing subsequence of the prefix $a[1 \ldots i]$ . I.e. we iterate over all $j$ such that $0 < j < i$ and $a_j < a_i$ . Among all such $j$ we take the maximum $dp(j)$ . Then $dp(i) = dp(j) + 1$ .

Therefore, we have the formula:

dp(i) = \text{max} \begin{cases} 1 \\ dp(j) + 1 & 0 < j < i, \ a_j < a_i \\ \end{cases}

The answer will be the maximum value of $dp(i)$ among all $i \ (1 \leq i \leq n)$ .

LIS with reconstruction

Let us, for each non-base state, remember the best transition just as in the case of LCS. I.e. we will also create an array $p(i)$ where we will store information about which transition was made. We know that $dp(i)$ has two different transitions:

$dp(i) = 1$ . I.e. it consists of one element. In this case we write $p(i):=0$ .
$dp(i) = dp(j) + 1$ for some $j$ . Then we write $p(i):=j$ .

After that we can reconstruct the answer. Find such an $x$ for which $dp(x)$ has the maximum value. And we will do the following until $x>0$ .

Include $a_x$ in the answer. Since by definition of the DP it is included in the answer. Next we make the transition to $x:=p(x)$ .

for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        p[i] = 0;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                p[i] = j;
            }
        }
    }

    int x = 1;
    for (int i = 1; i <= n; i++) {
        if (dp[i] > dp[x]) {
            x = i;
        }
    }

    vector<int> res;
    while (x > 0) {
        res.push_back(a[x]);
        x = p[x];
    }
    reverse(res.begin(), res.end());