Longest increasing subsequence

Tags: ,

Given an array of integers, find the longest increasing subsequence i.e a subsequence such that every element of subsequence satisfy this condition: i < j  and a[i] < a[j].

Input: 
[3, 10, 2, 1, 20 ]
Output: 
3
Explanation:
The longest increasing subsequence is 3, 10, 20

Input:
[ 3, 2 ]
Output: 
1
Explanation:
The longest increasing subsequences are {3} and {2}

Input: 
[ 50, 3, 10, 7, 40, 80 ]
Output:
4
Explanation:
The longest increasing subsequence is {3, 7, 40, 80}

Longest common subsequence : thought process

If we have to find the longest increasing subsequence till the last element of an array, i.e nth element, the question is does that depend on LIS till n-1 elements before it? Idea is to see if any increasing subsequence already present till current index i,  can include  A[i] and still remain increasing? To confirm that, check every element at index j such that j>=0 and j < i and A[j] < A[i].

If A[j] is less than A[i], then A[i] can be part of increasing subsequence ending with element j. The length of such increasing subsequence can be (length of increasing subsequence ending at j )+1. Check for each such element and take maximum length. Let’s see an example and see how it works.

Before we start a solution, let’s think why are we applying dynamic programming here. First because, the solution to a bigger problem depends on the optimal solution of subproblems and second, because if we do not store solutions to subproblems we may end up calculating them again and again. Both Optimal subproblem property and overlapping subproblem property are satisfied with this problem and hence we will use dynamic programming to solve it.

LIS[i] will represent the longest increasing subsequence length till element i .

LIS[i] = 1 + max(LIS[j]) for all  0<=j<i and A[j]<A[i] 
       = 1 if no such element exists where j< i and A[j]<A[i]

Click here to see the implementation

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

Let’s take an example and see how this code works? For example, given array A = {2,4,6,3,5,7,9}

Initialize LIS[0] =1, that means there is an increasing subsequence of length 1 at index 0.
For i = 1 i.e 4, check for j=0 to 1, excluding index 1. A[0] < A[1], hence LIS length is 2 (LIS[0] + 1 ).

For i = 2, i.e. 6 , check j = 0 to 2.  and check that LIS[0] = 1 and LIS[1] =2. Max LIS[j] for j=0 to  2 is 2. LIS[2] = 3 (LIS[1] +1).
For i =3 i.e 3, check from 0 to 3, Max LIS till index 3 will be LIS[3] = 2 because only A[0] is less than A[3]. Hence longest subsequence ending with i = 3 will have length only of 2.  LIS[3] = 2
For i = 4, i.e.5 Max LIS is again 3 which includes {2,4,5} or {2,3,5}
For i = 5, i.e 7, Max LIS is 4 which includes {2,4,5,7} or {2,3,5,7} or {2,4,6,7}
For i = 6, i.e 9, Max LIS is 5 which includes {2,4,5,7,9} or {2,3,5,7,9} or {2,4,6,7,9}

Therefore, the longest increasing subsequence is 6 for a given array.

Other problems which are a variance of longest increasing subsequence and can be solved by finding the longest increasing subsequence are :

1. Given two river banks (visualization: two parallel lines), one bank has numbers written (1….n) in sorted order. On the other bank, the numbers (1…n) are arranged randomly. A bridge can be formed from the ith point from bank 1 to ith point in bank 2. Find the max number of non-intersecting bridges you can form?
Just find the longest increasing subsequence in unordered number and that will be the solution.

2. Given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i), and depth d(i) (all real numbers). You want to create a stack of boxes that are as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

3. Another problem which borrow heavily from approach is find longest zigzag subsequence in an array

Algorithm to find longest increasing subsequence works in O(n2) in time complexity with O(n) space complexity.

Please share if you find anything wrong or missing, we would love to hear from you. If you want to be part of editors and contributors team at Algorithms and Me, please drop us an email at [email protected]