DP: Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Note: The subsequence is not necessarily unique or contiguous.

In this post, I'll be solving classic DP problem which involves finding lis of a given array as well as some of its variations.

The problems related to LIS that I'll be seeing are :

1. https://leetcode.com/problems/longest-increasing-subsequence/
2. https://www.interviewbit.com/problems/longest-increasing-subsequence
3. https://leetcode.com/problems/number-of-longest-increasing-subsequence/
4. https://www.interviewbit.com/problems/length-of-longest-subsequence/

Problem 1 and 2:

Let's see problem 1 and 2. Both the problems are similar. The task is to find the length of the longest increasing(strictly) subsequence.

eg: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

 Here length of LIS = 6. 

We can have multiple LIS with maximum length, but in this problem we are not concerned about the number of longest increasing subsequence(which we will see in 3rd problem here).


I'm gonna dive directly into bottom up approach for solving LIS in O(n ^ 2).

Approach:

Let's observe few scenarios.

A = [1 ,2 ,3, 4, 5]
If we have such array, then how can we find LIS upto length 1... 5. We're gonna need some kind of array to store those values. Let's say we make an array of size that of the given array and initialize with 1 as it is guaranteed that the minimum LIS for an array of length greater than 0 is always 1(Case when there is only 1 element)

What will be the approach to find lis upto index i????
Obviously we have to look at index from j = 0 to i - 1 and see if we can improve by taking element at index j such that element A[j] < A[i]

This roughly translates to below snipppet: lis[i] = max(lis[i], 1 + lis[j])
After building the LIS table , we can return the maximum value from the lis array

Implementation

int Solution::lis(const vector<int> &A) {
    // If the array is empty
    if(A.size() == 0){
            return 0;
        }
        // Initialize lis array with 1
        vector<int> lis(A.size(), 1);
        
        for(int i = 0; i < A.size(); i++){
            for(int j = 0; j < i; j++){
                // If jth element can be taken 
                // Maximize lis upto index i
                if(A[j] < A[i]){
                    lis[i] = max(lis[i], 1 + lis[j]);
                }
            }
        }
        return *max_element(lis.begin(), lis.end());
}