Longest increasing subsequence : Dynamic Programming

Longest increasing subsequence

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].For example, in array {2,4,6,3,5,7,9} longest increasing subsequence is of length 5  = {2,4,6,7,9} longest increasing subsequence
More examples :

Input  : arr[] = {3, 10, 2, 1, 20}
Output : Length of LIS = 3
The longest increasing subsequence is 3, 10, 20

Input  : arr[] = {3, 2}
Output : Length of LIS = 1
The longest increasing subsequences are {3} and {2}

Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing subsequence is {3, 7, 40, 80}

Longest common subsequence : Line of Thoughts

We have to find longest increasing subsequence till last element of array, i.e Nth element, question is does depend on LIS till N-1 element? 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 element A[j] is less than A[i], then A[i] can be part of increasing subsequence ending with element j. 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 solution,, let’s think why are we applying dynamic programming here. First because, solution to bigger problem depends on 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 for this problem and hence we will use dynamic programming to solve it.

Longest increasing subsequence : Implementation

Define an array LIS of size N, LIS[i] will represent 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]

Below is C code to implement it.

#include <stdio.h>
#include <stdlib.h>

int maximumLIS(int a[], int end, int *lis){
    for (int i=0; i<end; i++){
        if( a[i] < a[end] && lis[i] > lis[end] )
            lis[end] = lis[i];
    }
    return lis[end];
}

int lis(int a[], int size){

    int *lis = (int *)malloc(sizeof(int)*size);
    lis[0] = 1;

    for(int i=1; i<size; i++){
    	lis[i] = 1 + maximumLIS(a,i,lis);
    }
    
    int result = lis[size-1];
    free(lis);
    
    return result;
}

int main(void) {
	int a[] = { 2,4,6,3,5,7,9 };
	int size = sizeof(a)/sizeof(a[0]);

	printf("Length of Longest increasing subsquence : %d" , lis(a, size));
	
	return 0;
}

Java implementation for the same algorithm

package com.company;

/**
 * Created by sangar on 7.1.18.
 */
public class LIS {

    private static int maximumLIS(int a[], int end, int [] LIS){
        for (int i=0; i<end; i++){
            if( a[i] < a[end] && LIS[i] > LIS[end] )
            LIS[end] = LIS[i];
        }
        return LIS[end];
    }

    private static int lis(int [] A){

        int [] LIS = new int[A.length];
        LIS[0] = 1;

        for(int i=1; i<A.length; i++){
            LIS[i] = 1 + maximumLIS(A,i,LIS);
        }

        return LIS[A.length - 1];
    }
    public static void main(String[] args) {
        int[] A = {2,4,6,3,5,7,9};
        System.out.println("Longest increasing sybsequence : " + lis(A));
    }
}

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, longest increasing subsequence is 6 for given array.

Other problems which are variance of longest increasing subsequence and can be solved by finding 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 longest increasing subsequence in non ordered 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 which is 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(N^2) 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 communications@algorithmsandme.com