Data Structures & Algorithms in Java – Dynamic Programming – Longest Increasing Subsequence

Problem:

Given an array of integers , find the length of the longest increasing subsequence.

Example:

Given the input:

[10,9,2,5,3,7,101,18]

The longest subsequence is [2,3,7,101] , so output is length 4

A subsequence is just a sequence of numbers from an array where you can remove numbers at any position.

Increasing subsequence means the numbers should be in increasing order.

Try out the solution here:

https://leetcode.com/problems/longest-increasing-subsequence/

Solution:

Hint:

• Can be solved using Dynamic Programming – find solution of a smaller sub problem and use it to find out the solution of the bigger problem
• For every index position , find out the longest increasing subsequence length and use this to calculate the increasing subsequence length of the next index.

Example:

Consider the input:

[0,3,1,6,2,2,7].

First initialize an output array of the same size as the input array.

The value at each index represents the longest increasing subsequence at that index.

Initially this value is set to 1, as in the worst case at least the element itself can be considered as a subsequence with the length 1.

output = [1,1,1,1,1,1,1]

Let’s start with the first element 0.

This is the first element so we dont update the longest increasing subsequence for this value and it remains 1.

….

Now lets take the second element 3.

3 is greater than 0.

So take the longest increasing subsequence value of 0 (which is 1) and add 1 to it.

1+1 = 2

This is the current longest subsequence length.

output = [1,2,1,1,1,1,1]

……

Now lets take the next element 1.

Take all the previous elements which is less than 1. We have 0 at the first index.

Add 1 to the longest subsequence value of 0 which is 1. 1+1 = 2

Update the current longest subsequence value to 2 for that index.

We also have the element 3 but it is greater than 1 so we ignore it.

output = [1,2,2,1,1,1,1]

……..

Now lets take the next element 6.

We have [0,3,1] sub array behind it.

All the elements are lesser than 6.

So take the longest subsequence length at each index , add 1 to it and find the maximum of these values. The result is 3. Store that in the current index.

[1,2,2,3,1,1,1]

Continue this until you reach the last element.

output = [1,2,2,3,3,3,4]

Now you have an output array with the longest subsequence length at each position . Find the longest of those values and return it (output – 4).

ALGORITHM:

STEP1: Declare an output array of the same size as the input array to store the longest increasing subsequence values at each index.

STEP2: Set the value as 1 for all the indices.

STEP3: For every element in the input array , compare the longest increasing subsequence length values of every other element before that element ( provided the element is greater than those values) . Choose the longest among them and update the longest increasing subsequence length value at the current index (after adding 1 to include the current element).

STEP4: Return the maximum value in the output array which represents the longest increasing subsequence.

Code:

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

Time complexity of above algorithm is O(n²) since we run two nested for loops.

Space complexity is O(n) since we use an output array of the same size as the input array.

A better solution of time complexity O(nlogn) exists.

It is also called Patience Sorting (wiki).

The basic idea is:

Imagine each number in the input array is a card with the given number.

First pick the first card and keep it on the table . This is the first pile.

Next pick the next card , if it is less than the first card , keep it on top of it , else create a new pile and keep there.

For every card you pick , compare from the left most pile , if it is less than the top card in the first pile , keep there , else compare with the next pile , see if is less than the top card in that pile , then keep there and so on until you reach the end of all the piles.

If there are no piles where you can keep the card on top (it is greater than all the top cards) create a new pile and keep there.

Finally the number of piles give you the longest increasing subsequence.

If you notice the top cards are all in increasing order.

The value of the top cards from the leftmost pile give you the sequence values.

In the below algorithm we just store the top card value ( by replacing it each time) instead of storing the entire pile.

ALGORITHM:

STEP1: Create an arraylist named pile

STEP2: For each element in the array , do a binary search on the pile. This will give the position of the element in the pile list.

STEP2a: If the element is greater than all the elements in the pile , add this element at the end.

STEP 2b: If the element is between two pile values , replace the second pile value with the new value (this represents the top card as explained in previous example)

STEP 3: Return the pile list length

Code:

We are using Collections.binarySearch() to find the element in the pile. If the element is present in the list it returns the index position.

For example , in the input array [1,2,3,4]

Searching for 3 returns the index value 2 since input[2] = 3

But if the element is not present then it will return the position where the element can be inserted

For example if the input array is [1,2,3,5] and you search for 4

It returns -4 as the element has to be inserted after the element 3 (in the fourth position starting from the first element)

Notice that the value is negative and also the position returned considers the first index as 1 instead of 0.

If you search for the value 6 in the above array ,

It returns -5 , since the element can be added to the end of the list.

class Solution {
    public int lengthOfLIS(int[] nums) {
        
        
        var piles = new ArrayList<Integer>();
        
        
        for(int i=0;i<nums.length;i++){
            
            
            int position = Collections.binarySearch(piles,nums[i]);
            
//element is greater than all the other elements , so create a new pile
            if(-position == piles.size()+1){
                
                
                piles.add(nums[i]);
            }
            
           // since Collections.binarySearch() returns a negative value and also an incremented index value for values not present , lets negate it for ease of calculation and convert them to the usual index in java arrays.
            if(position < 0){
                
                position = (-position) -1;
            }
            
// if the element is present between two values (two piles) replace the old value with the new one (replace the top card)
            if(position < piles.size()){
                
                piles.set(position,nums[i]);
            }
            
            
        }
        

        return piles.size();
    }
}

That’s it!