Longest Increasing Subsequence

📌 Example: [10, 9, 2, 5, 3, 7, 101, 18]

LIS: [2, 5, 7, 101] → Length = 4 (other answers of length 4 exist, such as [2, 3, 7, 101])

Patience sorting LIS achieves O(n log n) time complexity.

O(n²) Dynamic Programming

Create a dp array where dp[i] = length of LIS ending at index i. For each i, check all previous j where nums[j] < nums[i] and take the maximum dp[j] + 1. Time complexity O(n²).

O(n log n) Patience Sorting

Maintain piles where each new number is placed on the leftmost pile with top card ≥ current number. The number of piles equals the LIS length. Use binary search for O(n log n) complexity.

Backtrack to Find LIS

After computing dp values, trace backwards to reconstruct the actual longest increasing subsequence, not just its length.

Python

from bisect import bisect_left

def lis_dp(nums):
    """O(n^2) DP. Returns the actual longest increasing subsequence."""
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n        # dp[i] = length of the LIS ending at i
    prev = [-1] * n     # prev[i] = index of the element before i in that LIS
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    end = max(range(n), key=lambda i: dp[i])   # where the best LIS ends
    seq = []
    while end != -1:
        seq.append(nums[end])
        end = prev[end]
    return seq[::-1]

def lis_length(nums):
    """O(n log n) patience sorting. Returns the length only."""
    tails = []          # tails[k] = smallest tail of any increasing run of length k+1
    for x in nums:
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)

print(lis_dp([10, 9, 2, 5, 3, 7, 101, 18]))      # [2, 5, 7, 101]
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

C++

#include <bits/stdc++.h>
using namespace std;

// O(n^2) DP that also rebuilds the actual subsequence
vector<int> lisDp(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};
    vector<int> dp(n, 1), prev(n, -1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
    int end = max_element(dp.begin(), dp.end()) - dp.begin();
    vector<int> seq;
    for (; end != -1; end = prev[end]) seq.push_back(nums[end]);
    reverse(seq.begin(), seq.end());
    return seq;
}

// O(n log n): length only (patience sorting with binary search)
int lisLength(const vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    for (int x : lisDp(nums)) cout << x << " ";   // 2 5 7 101
    cout << "\nlength = " << lisLength(nums) << "\n";  // 4
}

Knapsack Visualizer

Visualize the 0/1 knapsack problem with DP table.

Coin Change Guide

Minimum coins and number of ways using DP.

Pumping Lemma Solver

Step-by-step proof assistant for pumping lemma.

GeeksforGeeks

Detailed LIS algorithm tutorial.