AntInLoop

Longest Increasing Subsequence (LIS)

Longest Increasing Subsequence finds the longest strictly increasing subsequence of an array in O(n^2) via classic DP or O(n log n) via patience sorting with binary search.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Longest Increasing Subsequence (LIS)

Given an array of $n$ numbers, the Longest Increasing Subsequence (LIS) problem asks for the length (or elements) of the longest subsequence $a_{i_1} < a_{i_2} < \dots < a_{i_k}$ with $i_1 < i_2 < \dots < i_k$. It has two classic solutions: an intuitive $O(n^2)$ DP and a sleek $O(n \log n)$ Patience Sorting + Binary Search algorithm.

At a Glance

| Approach | Time | Auxiliary Space |

| :--- | :--- | :--- |

| Classic 1D DP | $O(n^2)$ | $O(n)$ |

| Patience Sorting + Binary Search | $O(n \log n)$ | $O(n)$ |

| Segment Tree / Fenwick Tree | $O(n \log n)$ | $O(n)$ (also counts LIS!) |

---

How It Works ($O(n \log n)$ Tails Method)

Maintain an array tails where tails[len - 1] stores the smallest possible ending value of an increasing subsequence of length len:

1. Note that tails is always strictly sorted!

2. For each element x in arr:

  • Find the first index pos where tails[pos] >= x using std::lower_bound (for non-decreasing subsequence, use std::upper_bound instead!).
  • If pos == tails.size(), append x; otherwise replace tails[pos] = x.

3. The final tails.size() is the exact LIS length.

procedure lisLength(A):
    tails = []
    for x in A:
        pos = lower_bound(tails, x)
        if pos == length(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return length(tails)

Step-by-Step Trace

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

  • 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]
  • Result: Length = 4 ([2, 3, 7, 18] or [2, 5, 7, 101]).

---

Complexity & Key Insights

  • Warning — tails Is NOT Always the Actual LIS! On [3, 4, 1], tails ends as [1, 4], which is not a valid subsequence (even though its length 2 is exact). To reconstruct the actual LIS in $O(n \log n)$, store the indices in tailsIdx plus a parent[i] array!
  • Strictly Increasing vs. Non-Decreasing:
  • Strictly increasing (<): use std::lower_bound.
  • Non-decreasing (<=): use std::upper_bound.
  • Dilworth's Theorem: The minimum number of non-increasing subsequences needed to cover an array equals the length of its Longest Strictly Increasing Subsequence!

---

Practice Problems

Easy

1. LIS Length in $O(n \log n)$ (LeetCode 300)

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Approach: Maintain tails with std::lower_bound. Time: $O(n \log n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails;
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return static_cast<int>(tails.size());
}

int main() {
    std::cout << lengthOfLIS({10, 9, 2, 5, 3, 7, 101, 18}) << "\n"; // 4
    return 0;
}

</details>

2. Reconstruct an Actual LIS in $O(n \log n)$

Return the actual elements of one Longest Increasing Subsequence (not just its length).

Approach: Store indices in tailsIdx and link each element i to parent[i] = tailsIdx[pos - 1] (when pos > 0). Walk backward from tailsIdx.back() and reverse. Time: $O(n \log n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> buildLIS(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    if (n == 0) return {};

    std::vector<int> tailsVal, tailsIdx, parent(n, -1);
    for (int i = 0; i < n; ++i) {
        auto it = std::lower_bound(tailsVal.begin(), tailsVal.end(), nums[i]);
        int pos = static_cast<int>(it - tailsVal.begin());
        if (it == tailsVal.end()) {
            tailsVal.push_back(nums[i]);
            tailsIdx.push_back(i);
        } else {
            *it = nums[i];
            tailsIdx[pos] = i;
        }
        if (pos > 0) parent[i] = tailsIdx[pos - 1];
    }

    std::vector<int> lis;
    for (int cur = tailsIdx.back(); cur != -1; cur = parent[cur]) {
        lis.push_back(nums[cur]);
    }
    std::reverse(lis.begin(), lis.end());
    return lis;
}

int main() {
    for (int x : buildLIS({3, 4, 1, 2, 8, 5, 6})) std::cout << x << " ";
    std::cout << "\n"; // 1 2 5 6
    return 0;
}

</details>

---

Intermediate

3. Number of Longest Increasing Subsequences (LeetCode 673)

Given an integer array nums, return how many distinct longest strictly increasing subsequences exist.

Approach: Track len[i] (best LIS length ending at i) and cnt[i] (number of LIS of length len[i] ending at i). For each j < i with nums[j] < nums[i], update len[i] and accumulate cnt[i]. Time: $O(n^2)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

int findNumberOfLIS(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    if (n == 0) return 0;

    std::vector<int> len(n, 1), cnt(n, 1);
    int maxLen = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                } else if (len[j] + 1 == len[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        maxLen = std::max(maxLen, len[i]);
    }

    int total = 0;
    for (int i = 0; i < n; ++i) {
        if (len[i] == maxLen) total += cnt[i];
    }
    return total;
}

int main() {
    std::cout << findNumberOfLIS({1, 3, 5, 4, 7}) << "\n"; // 2
    return 0;
}

</details>

4. Longest Bitonic Subsequence

Find the length of the longest subsequence that first strictly increases and then strictly decreases.

Approach: Compute inc[i] (LIS ending at i from the left) and dec[i] (LIS ending at i from the right). The answer is max(inc[i] + dec[i] - 1) over all peaks i. Time: $O(n \log n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<int> lisPrefixLengths(const std::vector<int>& a) {
    std::vector<int> tails, res(a.size());
    for (size_t i = 0; i < a.size(); ++i) {
        auto it = std::lower_bound(tails.begin(), tails.end(), a[i]);
        int pos = static_cast<int>(it - tails.begin());
        if (it == tails.end()) tails.push_back(a[i]);
        else *it = a[i];
        res[i] = pos + 1;
    }
    return res;
}

int longestBitonic(const std::vector<int>& a) {
    auto inc = lisPrefixLengths(a);
    std::vector<int> rev(a.rbegin(), a.rend());
    auto decRev = lisPrefixLengths(rev);
    int n = static_cast<int>(a.size()), best = 0;
    for (int i = 0; i < n; ++i) {
        best = std::max(best, inc[i] + decRev[n - 1 - i] - 1);
    }
    return best;
}

int main() {
    std::cout << longestBitonic({1, 11, 2, 10, 4, 5, 2, 1}) << "\n"; // 6
    return 0;
}

</details>

---

Hard

5. Russian Doll Envelopes (2D LIS, LeetCode 354)

Given envelopes (width, height), one envelope fits inside another iff both width and height are strictly smaller. Find the maximum number of nested envelopes.

Approach: Sort by width ascending, and for equal widths sort by height descending! Sorting equal widths descending ensures two envelopes with the same width can never both be picked in an increasing height subsequence—reducing 2D nesting directly to 1D LIS on heights in $O(n \log n)$!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

int maxEnvelopes(std::vector<std::pair<int, int>> envelopes) {
    std::sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second; // descending height for equal widths!
    });

    std::vector<int> tails;
    for (const auto& [w, h] : envelopes) {
        auto it = std::lower_bound(tails.begin(), tails.end(), h);
        if (it == tails.end()) tails.push_back(h);
        else *it = h;
    }
    return static_cast<int>(tails.size());
}

int main() {
    std::cout << maxEnvelopes({{5, 4}, {6, 4}, {6, 7}, {2, 3}}) << "\n"; // 3
    return 0;
}

</details>

---

Related Algorithms