Longest Increasing Subsequence (LIS)

A subsequence preserves index order but may skip entries. LIS maximizes its length subject to strictly increasing values. The direct endpoint DP teaches state design; the tails optimization summarizes dominated endpoints to reduce runtime. We include both runnable versions and reconstruct one valid subsequence, emphasizing that the tails array alone need not be an actual subsequence.

Prerequisites: Binary Search; reconstruction; dominance. Related existing lessons: Linear Search and Binary Search.

Build the idea

1. Recognize the repeated subproblems

   Every choice of increasing indices can branch exponentially, but many histories end at the same entry. The future only needs the last value and achieved length. For n up to 5000 the quadratic DP is practical; for 200000 entries it is not, motivating a stronger representation. Sorting the input itself would destroy index order and solve a different problem.

2. Define the state

   The direct state D[i] is longest strictly increasing subsequence ending exactly at index i. The optimized state tails[len−1] is the smallest possible final value of any increasing subsequence of length len in the processed prefix. last[len−1] stores the input index achieving that tail, and parent[i] connects its witness to an earlier endpoint.

3. Derive the transition

   Directly, D[i]=1+max D[j] over j<i and a[j]<a[i], with empty maximum zero. For tails, lower_bound finds the first ending value≥a[i]. Replace it by a[i], or append if no such tail exists. A smaller endpoint for the same length is never worse for future extension. Store parent[i]=last[p−1] before replacing the current tail entry.

4. Base cases and computation order

   Process indices left to right. Each direct state starts at one for the singleton; an empty input has length zero. tails begins empty. lower_bound enforces strict increase because equal values replace, not extend; upper_bound gives the non-decreasing variant. Backtrack input parent indices from the last tail index and reverse, rather than printing unrelated tail entries as the witness.

5. Correctness and invariant

   The endpoint recurrence partitions an increasing subsequence by its penultimate entry, establishing the direct DP. The tails invariant keeps one nondominated endpoint per length; every append has a real earlier witness, while replacement preserves the length and only improves extendability. Binary search is valid because these minimal ending values are strictly increasing. Parent indices always point to earlier input positions.

6. Work the example

   For [3,1,2,5,4,6], tails evolves [3]→[1]→[1,2]→[1,2,5]→[1,2,4]→[1,2,4,6]. The optimized witness is 1,2,4,6; quadratic tie choices can return 1,2,5,6. Both have optimal length four. Different optimal sequences are acceptable unless an additional tie objective is requested.

   processed entry	tails
   3	3
   1	1
   2	1,2
   5	1,2,5
   4	1,2,4
   6	1,2,4,6

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>a(n),tails;
    std::vector<int>last,parent(n,-1);
    for(auto&x:a){
        std::cin>>x;
    }
    for(int i=0;i<n;++i){
        int p=std::lower_bound(tails.begin(),tails.end(),a[i])-tails.begin();
        if(p){
            parent[i]=last[p-1];
        }
        if(p==(int)tails.size()){
            tails.push_back(a[i]);
            last.push_back(i);
        }
        else{
            tails[p]=a[i];
            last[p]=i;
        }
    } // Smallest ending value for each length; tails itself need not be a subsequence.
    std::vector<long long>answer;
    for(int i=last.empty()?-1:last.back();i!=-1;i=parent[i]){
        answer.push_back(a[i]);
    }
    std::reverse(answer.begin(),answer.end());
    std::cout<<answer.size()<<'\n';
    for(int i=0;i<(int)answer.size();++i){
        std::cout<<answer[i]<<(i+1==(int)answer.size()?'\n':' ');
    }
    if(answer.empty()){
        std::cout<<'\n';
    }
}

Complexity analysis

Direct DP: n states, up to n predecessors each, O(n²) time/O(n) values/parents. Tails version: n binary searches over at most n lengths, O(n log(n+1)) time/O(n) storage including reconstruction. The sequence length fits int; values use long long.

Example input and output

Read n (0..200000), then n integers within ±10^9. Print strict LIS length and one witness sequence. The supplementary quadratic version uses n≤5000.

Input

6
3 1 2 5 4 6

Output

4
1 2 4 6

For [3,1,2,5,4,6], tails evolves [3]→[1]→[1,2]→[1,2,5]→[1,2,4]→[1,2,4,6]. The optimized witness is 1,2,4,6; quadratic tie choices can return 1,2,5,6. Both have optimal length four. Different optimal sequences are acceptable unless an additional tie objective is requested.

Read n (0..5000),then n integers within ±10^9. Print strict LIS length and a witness.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>a(n);
    for(auto&x:a){
        std::cin>>x;
    }
    std::vector<int>dp(n,1),parent(n,-1);
    int best=-1;
    for(int i=0;i<n;++i){
        for(int j=0;j<i;++j){
            if(a[j]<a[i]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
                parent[i]=j;
            }
        }
        if(best==-1||dp[i]>dp[best]){
            best=i;
        }
    } // dp[i] ends exactly at entry i.
    std::vector<long long>answer;
    for(int i=best;i!=-1;i=parent[i]){
        answer.push_back(a[i]);
    }
    std::reverse(answer.begin(),answer.end());
    std::cout<<answer.size()<<'\n';
    for(int i=0;i<(int)answer.size();++i){
        std::cout<<answer[i]<<(i+1==(int)answer.size()?'\n':' ');
    }
    if(answer.empty()){
        std::cout<<'\n';
    }
}

Input

6
3 1 2 5 4 6

Output

4
1 2 5 6

The direct DP keeps the earlier optimal predecessor on ties,so it may print a different length-four witness from tails.

Complexity: n endpoint states,up to n predecessors each:O(n²) time and O(n) storage.

Practical applications

Use for order-preserving sequence optimization and reductions to chains. LCS compares two sequences; LIS can be faster when the ordering is by a single comparable value. Extra constraints may invalidate one-tail-per-length dominance.

Check your understanding

Why replace a tail by a smaller value at the same length?

Put it into practice

Enumerate all subsequences for short arrays with duplicates and compare lengths.