LIS

The longest increasing subsequence (LIS) problem is one of the most common in competitive programming. Given a sequence A, we want to find some sequence A_1, A_2 … A_k such that A_1 < A_2 < A_3 < A_k, hence a strictly increasing subsequence. Additionally, we want to find the subsequence with the maximum possible length. 

Naively, we can do this task with O(N^2) dynamic programming. 

Let dp[i] = maximum length subsequence ending at index i

dp[0] = 0 

Then dp[i] = max(dp[j]) + 1 such that j < i and a[j] < a[i]. 

int lis(vector<int> a){     vector<int> dp(a.size());     for(int i = 0; i < a.size(); i++){         dp[i] = 1; //length is always at least 1          for(int j = 0; j < i; j++){             if(a[i] > a[j]){                 dp[i] = max(dp[i], dp[j] + 1);             }         }     }     return *max_element(dp.begin(), dp.end()); }

Fast solution: O(NlogN)

Let d_j[i] = the smallest element of A such that there exists an increasing subsequence of length i ending in said element. (If we only consider the prefix of elements up to index j). 

For example if we have the sequence A = {1, 5, 3, 4}

Then d_3 = {-INF, 1, 3, INF}. This is because a sequence of length 0 will always end with smallest element -INF, a sequence of length 2 is {1, 3} which ends with 3 which is minimal, etc. 

Notice that d_j is always increasing. 

Next, notice that when we want to calculate the LIS for the prefix ending at index i+1, then the answer will be the least j such that d_i[j] >= A[i+1]. This is because after we cannot extend the sequence further since all elements are larger than A[i+1]. 

Also note that we only update one index every single time we process a new value of d_i, so we can dynamically maintain d. 

int lis(vector<int> a){     vector<int> dp;     for(int u : a){         int p = lower_bound(dp.begin(),dp.end(), u) – dp.begin(); //find first greater than equal to         if(p == dp.size())dp.push_back(p); //extend the sequence         else dp[p] = u; //make the ending smaller       }     return dp.size(); }