Longest Increasing Sequence (LIS)

Given a list of numbers (or elements of any type which can be compared) we are supposed to find a sub-sequence of numbers which are strictly increasing.

For example:

input = {1, 4, 5, 6, 3, 2, 9}
LIS = {1, 4, 5, 6, 9}

There can be many LIS for a particular input. Just to point it out that sub-sequence does not require elements to be consecutive but to only follow the same relative order(basically you cannot shuffle the elements).

Dynamic Programming

int lengthOfLIS(vector<int>& input) {
    vector<int> lookup;
    lookup.resize(input.size());
    
    lookup[0] = 1;
    for(int i = 1; i < input.size(); i ++){
        int max = INT_MIN;
        for(int j = 0; j < i; j ++){
            if(input[j] < input[i]){
                if(lookup[j] > max){
                    max = lookup[j];
                }
            }
        }
        
        if(max == INT_MIN){
            lookup[i] = 1;
        }
        else{
            lookup[i] = max + 1;
        }
    }
    
    return max;
}

We can take another auxiliary array to store the index of the previous element for each element that is part of the LIS.

Time Complexity: O(n^2)

Space Complexity: O(n + n) [One for storing the length of the LIS and other one for getting actual LIS].

Patience Sorting

This technique can be best explained with the help of an example.

input = {1, 4, 5, 6, 3, 2, 9}

Create n buckets or vectors where n is the size of the input. Insertion into the bucket follows a very strict rule: 1. Only add elements to the end of the vector. Buckets acts more like stack. 2. For a particular bucket only smaller elements can be added. For example, if 5 has been added to a particular bucket, then only elements smaller than 5 can be added to that bucket.

Go through all the elements of the input one by one. 
Find the left most bucket that satisfies the above mentioned rules.

A naive implementation of the above algorithm will have O(n^2) time complexity. But it can be improved if we can use binary search to find the left most bucket.

Let's denote the buckets with B
input = {1, 4, 5, 6, 3, 2, 9}
B[0] = {}, B[1] = {}, B[2] = {}, B[3] = {}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 1: 
B[0] = {1}, B[1] = {}, B[2] = {}, B[3] = {}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 2: 
B[0] = {1}, B[1] = {4}, B[2] = {}, B[3] = {}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 3: 
B[0] = {1}, B[1] = {4}, B[2] = {5}, B[3] = {}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 4: 
B[0] = {1}, B[1] = {4}, B[2] = {5}, B[3] = {6}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 5: 
B[0] = {1}, B[1] = {4, 3}, B[2] = {5}, B[3] = {6}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 6: 
B[0] = {1}, B[1] = {4, 3, 2}, B[2] = {5}, B[3] = {6}, B[4] = {}, B[5] = {}, B[6] = {}

Iteration 7:
B[0] = {1}, B[1] = {4, 3, 2}, B[2] = {5}, B[3] = {6}, B[4] = {9}, B[5] = {}, B[6] = {}

Length of LIS = Number of non empty buckets.
LIS = Take last element from each bucket(It is only one of the many LIS)

Time Complexity: O(n lg n)

Space Complexity: O(n)