Longest Increasing Subsequence - LIS using Dynamic Programming

We are provided with an array of integers that is unsorted and we have to find the longest increasing subsequence.

The subsequence need not be consecutive
The subsequence shall be increasing

Let’s understand that better by a few examples.

Table of Contents

Example

Input

[9, 2, 5, 3, 7, 10, 8]

Output

Explanation

The longest increasing subsequence is [2,3,7,10].

Approach 1: Brute Force

This approach involves looking into all possible subsets and finding the longest subsequence that is increasing in nature.

Now, there may be two cases every time we visit the ith integer in an array.

It can either be included in the subsequence i.e it is bigger than the previous element
It is smaller than the previous element and cannot be included in the subsequence

But no matter if we include the element at a certain position or not there exists an increasing subsequence of a certain length up to that point and we can return the maximum length incurred till that point of time. Let’s understand that better by a code snippet(In Java and C++)

Java Program for Longest Increasing Subsequence

class Solution 
{
    public int helper(int[] nums,int prev,int cur)
    {
        if(cur==nums.length)
            return 0;
        int on_include=0;
        //If the element at current index is greater than 
        //previous element we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(Math.max(on_include,on_ignore));
    }
    public int lengthOfLIS(int[] nums) 
    {
        int max=helper(nums,Integer.MIN_VALUE,0);
        return max;
    }
}

C++ Program for Longest Increasing Subsequence

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int helper(vector<int> nums,int prev,int cur)
    {
        if(cur==nums.size())
            return 0;
        int on_include=0;
        //If we are greater than previous length we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(max(on_include,on_ignore));
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
     int max=helper(nums,-1,0);
        return max;    
    }
};

Complexity Analysis

Time Complexity

O(n^2) where N is the size of the array. Here we run two for loops which leads us to O(N*N) time complexity.

Space Complexity

O(1) because we use some variables which leads us to constant space c0mplexity.

Approach 2: Dynamic Programming

Let’s find the longest increasing subsequence for [9, 2, 5, 3, 7, 10, 8, 7].

Let’s create an array of the size of the integer array
Each element is a subsequence of at least length one i.e numbers themselves thus initialize the array with one.
1 1 1 1 1 1 1 1
For every ith position, we look at the jth position before it
If a[j]<a[i] then the subsequence at that position can be modified as the maximum of the length till jth and ith point.
For i=2, we look through i=0 and i=1 for the same. Let’s look at the modified array after the operations
1 1 Max(j+1,i)
(2)
1 1 1 1 1
The final array after all the comparisons can be looked into as :
1 1 2 2 3 4 4 3
Finding the maximum of all the numbers we find out the length of the maximum subsequence to be 4. Let’s understand this better by a code.

Java Program for Longest Increasing Subsequence

class Solution 
{
    public int lengthOfLIS(int[] nums) 
    {
        int ans[]=new int[nums.length];
        for(int i=0;i<ans.length;i++)
            ans[i]=1;
        for(int i=1;i<nums.length;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=Math.max(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<ans.length;i++)
        {
            max=Math.max(ans[i],max);
        }
        return max;
    }
}

C++ Program for Longest Increasing Subsequence

class Solution 
{
public:
    int cmax(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
    int ans[nums.size()];
    int i,j;
        for(i=0;i<nums.size();i++)
            ans[i]=1;
        for(i=1;i<nums.size();i++)
        {
            for(j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=cmax(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<nums.size();i++)
        {
            max=cmax(ans[i],max);
        }
        return max; 
    }
};

Complexity Analysis

Time Complexity

The time complexity of the above solution is O(n^2).

Space Complexity

O(n) because we use an array for storing the answer after each index.

References