LIS (Longest Increasing Subsequence)

Concept

LIS finds the length of the longest strictly increasing subsequence in an array. The O(n log n) approach maintains a list where p[i] is the smallest tail element of all increasing subsequences of length i+1. Use binary search (lower_bound) to find where each new element fits.

When to Use

• ▸Finding the longest increasing subsequence
• ▸Problems reducible to LIS (e.g., box stacking, longest chain)
• ▸When O(n^2) DP is too slow and you need O(n log n)
• ▸Patience sorting

Intuition

Maintain a list of 'best possible tails'. For each new number, if it's larger than everything in the list, extend the list. Otherwise, find the first element >= it and replace that element. This keeps the tails as small as possible, maximizing future extension potential. The list length at the end = LIS length. Think of it as playing patience (card game) — each pile's top card is as small as possible.

Complexity

Template Code

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

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];

    vector<int> p;
    for(int x : nums){
        int idx = lower_bound(p.begin(), p.end(), x) - p.begin();
        if(idx == p.size()) p.push_back(x);
        else p[idx] = x;
    }

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

    return 0;
}

// Sample Input:
// 8
// 10 9 2 5 3 7 101 18
//
// Sample Output:
// 4