⚙️AlgorithmIntermediate

Longest Increasing Subsequence

Key Points

  • •
    The Longest Increasing Subsequence (LIS) is the longest sequence you can extract from an array while keeping the original order and making each next element strictly larger.
  • •
    A simple dynamic programming solution runs in O() time and is easy to understand and reconstruct the sequence from.
  • •
    A faster O(n n) approach uses the patience sorting idea and binary search to maintain minimal possible tails for subsequences of each length.
  • •
    To reconstruct the actual LIS in O(n n), keep predecessor links and the index of the best tail for every length.
  • •
    Use lowe for strictly increasing LIS and uppe for non-decreasing LIS (allowing equal neighbors).
  • •
    The tails array stores the smallest ending value for any increasing subsequence of a given length, which guarantees optimal extension.
  • •
    Common pitfalls include confusing subsequences with subarrays and using the wrong bound (lower vs upper) when duplicates appear.
  • •
    LIS is a core subroutine for scheduling, versioning constraints, and 2D problems after sorting and reducing to 1D LIS.

Prerequisites

  • →Arrays and indexing — LIS is defined over sequences and uses random access into arrays.
  • →Binary search — The O(n log n) method relies on lower_bound or upper_bound on a sorted structure.
  • →Big-O notation — To compare O(n^2) DP with O(n \log n) patience-based algorithm.
  • →Dynamic programming basics — The O(n^2) recurrence and path reconstruction are classic DP patterns.
  • →C++ STL algorithms and vectors — Implementations use std::vector, std::lower_bound, and std::upper_bound.
  • →Stable sorting and tie-breaking (optional) — Needed when reducing 2D problems to 1D LIS (e.g., sort by one key and tie-break by the other).

Detailed Explanation

Tap terms for definitions

01Overview

The Longest Increasing Subsequence (LIS) problem asks: given an array of numbers, what is the longest subsequence (not necessarily contiguous) whose elements are strictly increasing? For example, in [3, 1, 2, 1, 8, 5, 6], one LIS is [1, 2, 5, 6] with length 4. The LIS is a classic problem because it embodies dynamic programming and greedy-plus-binary-search techniques, with both intuitive and efficient solutions. There are two main approaches. The first is an O(n^2) dynamic programming method where for each position i we compute dp[i], the best length ending at i, by looking back at all j < i with a[j] < a[i]. The second is an O(n \log n) method based on the patience sorting analogy: maintain an array tails such that tails[k] is the smallest possible tail of any increasing subsequence of length k+1, and update it using binary search. The LIS shows up in many disguises: as a building block in 2D problems (like envelopes nesting), as a way to measure disorder, and as a tool to enforce precedence constraints. Beyond just finding the length, we often need to reconstruct an actual sequence, which requires tracking predecessor indices along with the tails.

02Intuition & Analogies

Think of arranging a set of boxes on a shelf from left to right such that each box is taller than the one before it. You want the longest possible lineup while keeping their original left-to-right order. You cannot move boxes around; you can only choose which ones to keep. The O(n^2) way is like scanning every new box and asking, "What’s the longest lineup I can end with this box if I attach it to the best earlier box that’s shorter?" This is slow but very straightforward. Now picture the patience sorting card game: you place cards into piles so that each pile’s top card is as small as possible for its pile height. The rule is: place a new card on the leftmost pile whose top is greater than or equal to it (for strictly increasing we use the first pile with top >= card, which is lower_bound). Each pile represents the tail value of some increasing subsequence length. Making a pile’s top as small as possible keeps your options open to grow longer sequences later. The number of piles at the end equals the LIS length. This idea leads to the O(n \log n) algorithm because finding the correct pile is a binary search. To actually retrieve the sequence, imagine attaching a "pointer" from every card to the card it extends; meanwhile, we also remember which card sits on top of each pile. After processing all cards, we follow the pointers from the top of the last pile backward to reconstruct the LIS. If you want to allow equal neighbors (non-decreasing subsequence), you change one rule: use the first pile whose top is strictly greater than the card (upper_bound), so equals stack together.

03Formal Definition

Given a sequence A = [, , , ], a subsequence is any sequence that can be derived by deleting zero or more elements without changing the order of the remaining elements. The Longest Increasing Subsequence (LIS) is a subsequence [a_{}, a_{}, , a_{}] such that < < and a_{} < a_{} < < a_{}, with k as large as possible. Define dp[i] as the length of the LIS that ends at index i. The classic recurrence is dp[i] = 1 + \{ dp[j] : 1 ,\ \}, with base case dp[i] = 1 if no such j exists. Then the LIS length is L = dp[i]. The O(n n) algorithm maintains an array tails where tails[] equals the minimum possible tail value of any increasing subsequence of length +1. Formally, after processing the prefix A[1..i], we maintain the invariant tails[0] < tails[1] < < tails[L-1], and for every , there exists an increasing subsequence of length +1 whose last element equals tails[]. For strictly increasing LIS, when inserting a new , we find p = \{ : tails[] \} and set tails[p] = , extending L if p equals current L. For the non-decreasing variant, replace by > (use uppe).

04When to Use

Use LIS when you need to preserve order while maximizing a monotonic property. Typical scenarios include: 1) Measuring how close a permutation is to being sorted (the longer the LIS, the fewer removals needed to make the array strictly increasing). 2) 2D problems that reduce to 1D LIS after sorting, such as Russian doll envelopes or longest chain of pairs; you sort by one coordinate and apply LIS (with careful tie-breaking) to the other. 3) Scheduling or dependency problems where tasks must follow an increasing key (e.g., start time, version number) and you want the longest feasible chain. 4) Competitive programming tasks that ask for either the LIS length, one LIS, or the number of LIS (the latter can be solved in O(n^2) DP or with segment trees/coordinate compression for faster solutions). 5) Streamed or large inputs where O(n^2) is too slow; the O(n \log n) algorithm is the right choice for n up to 2e5 or more. Choose the O(n^2) DP when n \le 2000 or when you prioritize simplicity and easy reconstruction. Choose O(n \log n) when n is large or time limits are tight. Use lower_bound for strictly increasing sequences and upper_bound for non-decreasing sequences (allow equals).

⚠️Common Mistakes

Common pitfalls include: 1) Confusing subsequences with subarrays: subarrays are contiguous; subsequences are not. Always keep index order but you can skip elements. 2) Using the wrong binary search: for strictly increasing LIS you must use lower_bound (first \ge x); for non-decreasing you must use upper_bound (first > x). Using the wrong one changes the variant you compute. 3) Forgetting to track predecessors when you need to reconstruct the actual LIS in O(n \log n). Just storing the tails values is not enough; you need arrays of indices and a prev[] link. 4) Mishandling duplicates: with duplicates and lower_bound, equal values will replace the same-length tail (correct for strictly increasing), but if you expected equal neighbors to be allowed, switch to upper_bound. 5) Believing tails stores an actual subsequence: tails holds minimal tail values, not a valid LIS by itself. 6) Off-by-one errors in reconstruction: store the index of the last element for each length, and when you place an element at position p, set prev[current_index] = last_index_of_length_(p-1) if p > 0. 7) Overwriting tail indices without updating prev accordingly. 8) Assuming LIS is unique: there can be multiple LIS; reconstruction methods typically return one of them based on processing order.

Key Formulas

LIS DP Recurrence

Explanation: The best LIS ending at position i is 1 (just a[i]) plus the best LIS ending at some earlier j with a[j] < a[i]. If no such j exists, dp[i] = 1.

LIS Length from DP

Explanation: The overall LIS length is the largest dp[i] across all positions. It aggregates the per-position bests into the global answer.

Lower-bound Placement (Strict LIS)

Explanation: To insert into tails for strictly increasing LIS, find the first index with value greater than or equal to . Replace it with ; if p equals the current length, append.

Upper-bound Placement (Non-decreasing)

Explanation: For the non-decreasing variant, use the first index with value strictly greater than , effectively allowing equal neighbors to stay in the same length.

Tails Monotonicity

Explanation: The tails array is strictly increasing; otherwise a shorter tail could replace a longer-length tail. This monotonicity enables binary search and proves optimality.

Time Complexities

Explanation: The quadratic DP checks all prior elements for each i, while the patience-based method uses a binary search over tails per element. The latter scales better for large n.

Counting Number of LIS (DP)

Explanation: If also counting how many LIS end at i, sum counts of all predecessors that can extend to i. The total number of LIS is the sum of cnt[i] where dp[i] equals the LIS length.

Complexity Analysis

The O() dynamic programming approach computes dp[i] by scanning all and checking whether a[j] < a[i]. Each of the n positions performs up to O(n) comparisons, resulting in O() time. Space usage is O(n) to store the dp array, and O(n) more if you track predecessors to reconstruct a sequence. This solution is simple and very fast in practice for n up to about 2000–5000, depending on time limits. The O(n n) method maintains a sorted array tails with length at most L (the LIS length). For each element a[i], we perform one binary search on tails—either lowe (strictly increasing) or uppe (non-decreasing)—and potentially update a constant number of arrays. This yields O( n) time per element, or O(n n) overall. The tails length never exceeds n, so space is O(n). For full reconstruction in O(n n), we additionally maintain two index arrays: tai[] stores the index of the array element serving as the current best tail for length +1, and prev[i] stores the predecessor index in the subsequence. This keeps space O(n) and does not alter time complexity. In terms of constants, the O(n n) approach is slightly more involved but scales to n in the hundreds of thousands. Note that the tails values do not form an actual LIS; they are a compact summary that preserves the option to build the LIS. Finally, the choice between lowe and uppe controls whether the algorithm computes strictly increasing or non-decreasing subsequences, a critical detail when duplicates are present.

Code Examples

O(n^2) DP with Reconstruction of One LIS
1#include <bits/stdc++.h>
2using namespace std;
3
4// Reads n and array, prints LIS length and one LIS using O(n^2) DP
5int main() {
6    ios::sync_with_stdio(false);
7    cin.tie(nullptr);
8
9    int n;
10    if (!(cin >> n)) return 0;
11    vector<long long> a(n);
12    for (int i = 0; i < n; ++i) cin >> a[i];
13
14    if (n == 0) {
15        cout << 0 << "\n\n";
16        return 0;
17    }
18
19    vector<int> dp(n, 1);        // dp[i] = LIS length ending at i
20    vector<int> prev(n, -1);     // prev[i] = predecessor index of i in the LIS
21
22    int bestLen = 1, bestEnd = 0;
23    for (int i = 0; i < n; ++i) {
24        for (int j = 0; j < i; ++j) {
25            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
26                dp[i] = dp[j] + 1;
27                prev[i] = j;
28            }
29        }
30        if (dp[i] > bestLen) {
31            bestLen = dp[i];
32            bestEnd = i;
33        }
34    }
35
36    // Reconstruct LIS by walking predecessors from bestEnd
37    vector<long long> lis;
38    for (int i = bestEnd; i != -1; i = prev[i]) lis.push_back(a[i]);
39    reverse(lis.begin(), lis.end());
40
41    cout << bestLen << "\n";
42    for (int i = 0; i < (int)lis.size(); ++i) {
43        if (i) cout << ' ';
44        cout << lis[i];
45    }
46    cout << "\n";
47    return 0;
48}
49

This quadratic DP checks all previous elements j for each i to decide whether appending a[i] to the best subsequence ending at j improves dp[i]. It also records predecessors to reconstruct an actual LIS at the end.

Time: O(n^2)Space: O(n)
O(n log n) Patience Sorting: Length of Strict LIS (lower_bound)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Reads n and array, prints the length of the strictly increasing LIS using tails + lower_bound
5int main() {
6    ios::sync_with_stdio(false);
7    cin.tie(nullptr);
8
9    int n;
10    if (!(cin >> n)) return 0;
11    vector<long long> a(n);
12    for (int i = 0; i < n; ++i) cin >> a[i];
13
14    vector<long long> tails; // tails[k] = minimal tail value of length k+1
15    tails.reserve(n);
16
17    for (long long x : a) {
18        // For strictly increasing LIS, use lower_bound: first element >= x
19        auto it = lower_bound(tails.begin(), tails.end(), x);
20        if (it == tails.end()) tails.push_back(x);
21        else *it = x;
22    }
23
24    cout << (int)tails.size() << "\n";
25    return 0;
26}
27

Maintains the minimal tail for each length and uses lower_bound to find where the current value fits. The size of tails at the end equals the LIS length.

Time: O(n log n)Space: O(n)
O(n log n) Strict LIS with Full Reconstruction (indices + predecessors)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Reconstructs one strictly increasing LIS in O(n log n)
5int main() {
6    ios::sync_with_stdio(false);
7    cin.tie(nullptr);
8
9    int n;
10    if (!(cin >> n)) return 0;
11    vector<long long> a(n);
12    for (int i = 0; i < n; ++i) cin >> a[i];
13
14    if (n == 0) {
15        cout << 0 << "\n\n";
16        return 0;
17    }
18
19    // tailsVal[ell] = minimal tail value for length ell+1
20    // tailsIdx[ell] = index in a[] of the element providing that tail
21    vector<long long> tailsVal;
22    vector<int> tailsIdx;
23    tailsVal.reserve(n);
24    tailsIdx.reserve(n);
25
26    // prev[i] = index of predecessor of a[i] in the LIS ending at i
27    vector<int> prev(n, -1);
28
29    for (int i = 0; i < n; ++i) {
30        long long x = a[i];
31        // Strictly increasing: lower_bound (first >= x)
32        int p = int(lower_bound(tailsVal.begin(), tailsVal.end(), x) - tailsVal.begin());
33        if (p == (int)tailsVal.size()) {
34            tailsVal.push_back(x);
35            tailsIdx.push_back(i);
36        } else {
37            tailsVal[p] = x;
38            tailsIdx[p] = i;
39        }
40        // Link to the last index of subsequence length p (which is at length p)
41        if (p > 0) prev[i] = tailsIdx[p - 1];
42    }
43
44    int L = (int)tailsVal.size();
45    // Reconstruct by starting from the last index of length L
46    int cur = tailsIdx[L - 1];
47    vector<long long> lis;
48    lis.reserve(L);
49    while (cur != -1) {
50        lis.push_back(a[cur]);
51        cur = prev[cur];
52    }
53    reverse(lis.begin(), lis.end());
54
55    cout << L << "\n";
56    for (int i = 0; i < (int)lis.size(); ++i) {
57        if (i) cout << ' ';
58        cout << lis[i];
59    }
60    cout << "\n";
61    return 0;
62}
63

This version keeps, for every length, the index of the array element that is currently the best tail. Each element i links to the last index used for length p (prev[i] = tailsIdx[p-1]). At the end, following prev from the best tail reconstructs the LIS.

Time: O(n log n)Space: O(n)
Non-decreasing Variant (LNDS) Using upper_bound
1#include <bits/stdc++.h>
2using namespace std;
3
4// Returns length of Longest Non-Decreasing Subsequence (allows equals)
5int main() {
6    ios::sync_with_stdio(false);
7    cin.tie(nullptr);
8
9    int n; 
10    if (!(cin >> n)) return 0;
11    vector<long long> a(n);
12    for (int i = 0; i < n; ++i) cin >> a[i];
13
14    vector<long long> tails; // minimal tail for each non-decreasing length
15    tails.reserve(n);
16
17    for (long long x : a) {
18        // Non-decreasing: place x after all <= x, i.e., first > x
19        auto it = upper_bound(tails.begin(), tails.end(), x);
20        if (it == tails.end()) tails.push_back(x);
21        else *it = x;
22    }
23
24    cout << (int)tails.size() << "\n";
25    return 0;
26}
27

Switching to upper_bound changes the rule to allow equal neighbors by placing x after all values <= x. This computes the longest non-decreasing subsequence length.

Time: O(n log n)Space: O(n)