Longest increasing subsequence

The longest increasing subsequence of an array is the longest list of its numbers that go up from left to right when the others are crossed out. The numbers don't have to stand next to each other; for the longest run of adjacent increasing numbers, one pass is enough. Dynamic programming finds it in O(n^2), and a sorted helper array with binary search finds it in O(n \log n).

Explanation

A row has 5 numbers: 3, 1, 4, 2, 5. Cross out as few numbers as possible so that the rest go up from left to right. Crossing out 3 and 4 leaves 1, 2, 5, which go up; no 4 numbers do, so the answer is 3.

Fig. 1. Arcs join the kept numbers 1, 2, 5. They go up from left to right.

The numbers that are left form a subsequence: some numbers of the row, in their original order, with gaps allowed. Several subsequences can share the longest length: 1, 4, 5 and 3, 4, 5 also have 3 numbers. Usually we need only the length, or any one of them.

Take a longer row: 4, 1, 9, 5, 2, 7, 6, 8. Each of the 8 numbers is kept or crossed out, so there are 2^8 = 256 ways to choose. For 50 numbers that is 2^{50}, about 10^{15} ways, too many to try.

The first thing to try is to go from the left and keep every number that is bigger than the last one kept. That keeps 4, skips 1, and keeps 9. Then it gets stuck: every number after 9 is smaller, so the result has 2 numbers, the red subsequence in Fig. 2. The blue subsequence 4, 5, 7, 8 has four. Starting from the smallest number, 1, doesn't help: the next bigger number is again 9.

Fig. 2. Keeping every number bigger than the last one gets stuck after 9 and keeps 2 numbers (red). The blue subsequence has 4.

Taking 9 was a mistake only because of the numbers after it. Remembering only the longest subsequence so far doesn't help either: after 4, 1, 9 it is 4, 9, and whether 5 can extend a subsequence of 2 numbers depends on where that subsequence ends, which its length doesn't tell us. So for every number we ask how long an increasing subsequence can be if it ends exactly at this number, and write this length under the number.

A subsequence that ends at 5 and has more than one number is a subsequence ending at a smaller number before 5, with 5 added. Before 5 come 4, 1 and 9. The number 9 is bigger, so 5 can't follow it. The lengths under 4 and 1 are 1 each, so 5 gets 1 + 1 = 2, for example 4, 5. A number with no smaller number before it, such as 4 or 1, starts its own subsequence and gets length 1. Going from left to right, every number we look back at already has its length written under it. The answer is the largest length under the row, not the one under the last cell.

This method is dynamic programming: from left to right, each number gets the largest length among the smaller numbers before it, plus 1.

Fig. 3 fills the whole row this way. The blue arc into each number comes from the number it follows.

4: there is no number before it, so 4 gets 1.

1: the only number before it, 4, is bigger, so 1 gets 1.

9: the smaller numbers before it are 4 and 1, both with length 1, so 9 gets 1 + 1 = 2. The blue cell is the smaller number with the largest length (the first one when there is a tie), the grey cells are the other smaller numbers.

5: the smaller numbers before it are 4 and 1, both with length 1, so 5 gets 2.

2: the only smaller number before it is 1, with length 1, so 2 gets 2.

7: the smaller numbers before it are 4, 1, 5 and 2; the largest length is 2, under 5, so 7 gets 3.

6: the smaller numbers before it are 4, 1, 5 and 2; 7 is bigger and doesn't count. The largest length is 2, under 5, so 6 gets 3.

8: every number before it except 9 is smaller; the largest length is 3, under 7, so 8 gets 4.

The largest length is 4, under 8. Following the chosen numbers back from 8 gives the subsequence 4, 5, 7, 8.

1/9

Fig. 3. The length of the longest increasing subsequence that ends at each number, filled from left to right.

Step through with the buttons or the arrow keys. The number under each cell is the length of the longest increasing subsequence that ends at it. The blue arc comes from the smaller number with the largest length, grey arcs from the other smaller numbers.:::

The run found the longest subsequence ending at every number of the row, for example 3 under 6 (4, 5, 6 or 1, 2, 6). The blue arcs are what the program stores to print the subsequence.

Keeping only the smallest ends

Each number looks back at every number before it: for 10^5 numbers that is about 5 \cdot 10^9 comparisons, far more than a second allows.

Look at the row after 4, 1, 9, 5, 2. There are subsequences of 2 numbers ending at 9, at 5 and at 2. Fig. 4 shows two of them. Any later number that can follow 9 or 5 is bigger than 5, so it can also follow 2. For subsequences of 2 numbers only the smallest end, 2, matters. So for each length we keep just one number: the smallest end of an increasing subsequence of that length found so far.

Fig. 4. The red subsequence ends at 5, the blue one at 2. 7 and 6 can follow both.

These smallest ends always go up: after 4, 1, 9, 5, 2 they are 1 for length 1 and 2 for length 2. A subsequence of 3 numbers contains one of 2 numbers whose end is smaller than its own, so the smallest end for 3 numbers is bigger than the smallest end for 2.

Because the ends are sorted, a binary search finds the first end that is not smaller than the new number. If there is none, the new number is bigger than all the ends and makes the longest subsequence one number longer. Otherwise it replaces that end: it can follow the end just before it, and it is a smaller end for that length. Take 7 after 4, 1, 9, 5, 2: the ends are 1 and 2, both smaller than 7, so 7 is added and the ends become 1, 2, 7.

Fig. 5 shows the ends after each number of the row.

Fig. 5. Each row shows the smallest end for each length after the number on its left. The amber cell is the one that number added or replaced.

After 8 the ends are 1, 2, 6, 8. There are four of them, so the longest increasing subsequence has 4 numbers again. The ends themselves are not always a subsequence. On the row 3, 4, 1 the ends become 1, 4, but 1 comes after 4 in the row, so 1, 4 is not a subsequence. Only the number of ends is the answer.

Implementation

The numbers are in an array a of n numbers, indexed from 0. dp[i] is the length under each cell in Fig. 3. To print the subsequence, par[i] is the index of the number before a[i] in that subsequence (the blue arc), or -1 when a[i] starts it.

In the names of the introduction:

1. State: dp[i] is the length of the longest increasing subsequence that ends at a[i].

2. Base case: dp[i] = 1, the number a[i] alone.

3. Order: i from left to right, so every dp[j] with j < i is already filled.

4. Transition: for each j < i with a[j] < a[i], if dp[j] + 1 > dp[i], set dp[i] = dp[j] + 1 and par[i] = j.

5. Answer: the largest dp[i]. Its index best is where the subsequence ends.

The input holds n, then the n numbers. The program prints the length, and then one longest increasing subsequence. For the main row the input is:

8
4 1 9 5 2 7 6 8

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int sign = 1;   // change to -1 for a decreasing subsequence
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] *= sign;
    }

    // state: dp[i] = the longest increasing subsequence that ends at a[i]
    vector<int> dp(n);
    vector<int> par(n, -1);   // only needed to print the subsequence

    // order: i from left to right
    for (int i = 0; i < n; i++) {
        // base case: a[i] alone
        dp[i] = 1;
        // transition: put a[i] after a smaller number a[j] before it
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {   // a[j] <= a[i] for a non-decreasing subsequence
                dp[i] = dp[j] + 1;
                par[i] = j;   // only needed to print the subsequence
            }
        }
    }

    // answer: the largest dp[i]
    int best = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[best]) best = i;
    }
    cout << dp[best] << "\n";

    // print the subsequence; remove this block if you only need the length
    vector<int> seq;
    for (int i = best; i != -1; i = par[i]) seq.push_back(sign * a[i]);
    for (int k = (int)seq.size() - 1; k >= 0; k--) {
        cout << seq[k] << (k > 0 ? ' ' : '\n');
    }
}

With sign = -1 every number is read with its sign flipped, so an increasing subsequence of the flipped numbers is a decreasing subsequence of the real ones, and sign * a[i] prints the real numbers back. With <= instead of <, equal neighbours are allowed. Both changes together give the longest non-increasing subsequence.

Walking back along par from best collects the subsequence from its end, so the program prints seq backwards. When several numbers give the same largest length, the strict > keeps the first one, and the program prints 4 5 7 8.

When each number has a weight and the task asks for the largest total weight of an increasing subsequence, the same program works with dp[j] + w[i] in place of dp[j] + 1 and dp[i] = w[i] as the base case. To count the increasing subsequences, set dp[i] to 1 plus the sum of dp[j] over the same j, usually modulo the number the problem gives. The answer is then the sum of all dp[i], not the largest: on the main row the counts are 1 1 3 3 2 8 8 24, 50 in total.

The two loops check every pair j < i, so the time is O(n^2) and the memory is $O(n)$. By the rule of thumb of about 10^8 simple steps per second, that is fine for n up to about 10^4.

Faster version for long arrays

The faster method keeps the vector tails: tails[k] is the smallest end of an increasing subsequence of length k + 1 found so far. For each a[i] there are two steps:

1. k is the index of the first element of tails that is not smaller than a[i]. This is what lower_bound returns: an iterator to that element, or tails.end() when every element is smaller, so subtracting tails.begin() gives k.

2. If k is the size of tails, append a[i]; otherwise set tails[k] = a[i].

The answer is the size of tails. To print a subsequence, tailIdx[k] keeps the index in a of the number in tails[k]. When a[i] goes to index k, it follows the number at tailIdx[k - 1], so that index becomes par[i]. The input is the same as above.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int sign = 1;   // change to -1 for a decreasing subsequence
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] *= sign;
    }

    vector<int> tails;     // tails[k] = the smallest end of an increasing subsequence of length k + 1
    vector<int> tailIdx;   // tailIdx[k] = the index of that end in a; only needed to print the subsequence
    vector<int> par(n, -1);   // only needed to print the subsequence

    for (int i = 0; i < n; i++) {
        // the first end that is not smaller than a[i]
        int k = lower_bound(tails.begin(), tails.end(), a[i]) - tails.begin();   // upper_bound for a non-decreasing subsequence

        // append a[i] or replace that end
        if (k == (int)tails.size()) {
            tails.push_back(a[i]);
            tailIdx.push_back(i);
        } else {
            tails[k] = a[i];
            tailIdx[k] = i;
        }
        if (k > 0) par[i] = tailIdx[k - 1];   // only needed to print the subsequence
    }

    cout << tails.size() << "\n";

    // print the subsequence; remove this block if you only need the length
    vector<int> seq;
    for (int i = tailIdx.back(); i != -1; i = par[i]) seq.push_back(sign * a[i]);
    for (int k = (int)seq.size() - 1; k >= 0; k--) {
        cout << seq[k] << (k > 0 ? ' ' : '\n');
    }
}

For the main row it prints 4 and then 1 2 6 8, a different longest subsequence from the one the O(n^2) program prints, and both are right. The number 8 goes to index k = 3 and follows tailIdx[2], which at that moment is the index of 6. The number 6 followed 2, and 2 followed 1. Later replacements change tailIdx, but not the indexes already stored in par.

Each number costs one binary search over at most n ends, so the time is O(n \log n) and the memory is $O(n)$, fine for n up to 10^6.

The faster method doesn't take weights. Take the numbers 1, 3, 2, 4 with weights 1, 100, 1, 1. After 1, 3, 2 the smallest end for 2 numbers is 2, with total weight 2. The subsequence 1, 3 with total 101 is forgotten, so the best total the method can give 4 is 2 + 1 = 3, while 1, 3, 4 weighs 102.

Correctness proof

The O(n^2) DP fills dp from left to right, and we assume every length before $i$ is right. Take a longest increasing subsequence ending at a_i. If it has only a_i, its length is 1, the base case. Otherwise let a_j be the number before a_i in it. Then j < i and a_j < a_i, and the part up to a_j is an increasing subsequence ending at a_j, so it has at most dp_j numbers. So the length is at most dp_j + 1, which the transition tries. Every length the transition writes is a real subsequence, the one ending at a_j with a_i added, so dp_i is never too big either. The longest subsequence of the whole row ends at some number, so the answer is the largest dp_i.

The faster method keeps one invariant: after each number, tails_k is the smallest end of an increasing subsequence of length k + 1 among the numbers seen so far, and the ends go up. One end per length is enough, because a later number that can follow some end of length k + 1 can also follow the smallest one.

Let a new number $x$ come, and let $k$ be the first index with tails_k \ge x. The subsequences that $x$ can extend are the ones whose end is smaller than $x$: the lengths 1 to $k$. The longest of them gives a subsequence of length k + 1 ending at $x$. Its end $x$ is at most tails_k, so $x$ becomes the new smallest end for that length. For every shorter length the old end is already smaller than $x$. No subsequence of length k + 2 or more ends at $x$, because the ends for k + 1 numbers and more are not smaller than $x$. So only index $k$ changes, and the ends still go up: tails_{k-1} < x \le tails_k < tails_{k+1}.

Common mistakes

• Keeping every number that is bigger than the last one kept. On 1, 5, 2, 3 it keeps 1 and 5 and gets 2, but 1, 2, 3 has 3 numbers. Whether a number is worth taking depends on the numbers after it, which only the DP looks at.

• Using best[i], the longest increasing subsequence among the first i + 1 numbers, with best[i] = max(best[i-1], best[j] + 1) over j < i with a[j] < a[i]. On 5, 6, 1, 2 it gives 1, 2, 2, 3: 2 follows 1, but best for 1 is 2 because of 5, 6, which 2 can't follow. The answer is 2. Use dp[i] for the subsequence that ends at a[i].

• Printing dp[n-1] as the answer. On 1, 2, 3, 0 the lengths are 1, 2, 3, 1, so dp[n-1] is 1, but the answer is 3. Take the largest dp[i].

• Mixing up lower_bound and upper_bound. On 2, 2, 2 with upper_bound the strict answer comes out as 3 instead of 1, because each new 2 is appended after the equal end. Use lower_bound for an increasing subsequence and upper_bound for a non-decreasing one.

Similar algorithms

The longest common subsequence is for two sequences: the longest subsequence of both. It fills a two-dimensional table in $O(nm)$. The longest increasing subsequence of an array of different numbers is the longest common subsequence of the array and its sorted copy, but that takes O(n^2) time and memory, slower than both methods above.

The O(n^2) DP is a longest path in a graph without cycles: draw an arrow from each number to every later, bigger number, and the longest increasing subsequence is the longest path, with the vertices in left-to-right order as a topological sort. When "can follow" is not a comparison of numbers, for example when each number must divide the next, a smaller end is not always better: the ends 2 and 3 both start a subsequence of 1 number, and a later 9 can follow 3 but not 2. Then only the O(n^2) DP works.

A Fenwick tree over the values, replaced by their ranks 1 to n, finds the largest total weight of an increasing subsequence, or the number of increasing subsequences, in O(n \log n). The smallest ends can't do either.

Practice