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
poswheretails[pos] >= xusingstd::lower_bound(for non-decreasing subsequence, usestd::upper_boundinstead!). - If
pos == tails.size(), appendx; otherwise replacetails[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 —
tailsIs NOT Always the Actual LIS! On[3, 4, 1],tailsends as[1, 4], which is not a valid subsequence (even though its length2is exact). To reconstruct the actual LIS in $O(n \log n)$, store the indices intailsIdxplus aparent[i]array! - Strictly Increasing vs. Non-Decreasing:
- Strictly increasing (
<): usestd::lower_bound. - Non-decreasing (
<=): usestd::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
- Binary Search — accelerates LIS from $O(n^2)$ to $O(n \log n)$.
- Longest Common Subsequence (LCS) — reduces to LIS on permutations.