Longest increasing subsequence in array

Longest increasing subsequence problem

Given an array of integers, find longest increasing subsequence in it, increasing subsequence is set of elements of array such that if i<j then a[i] < a[j]. For example, in array [ 2,4,6,3,5,7,9 ], longest increasing subsequence is  [ 2,4,6,7,9 ] with length 5.

Brute force solution is to find all possible subsequences of an array and check each one of them for increasing subsequences and then output the longest one.  Number of subsequence of an array with length n is 2n. SO, solution has exponential complexity.

Can we do it in polynomial complexity? First of all, try to break problem into smaller and then work the solution up. To find longest subsequence till A[i], can solution till A[i-1] help?
Idea is to find if longest subsequence already present before a particular element A[i], can include A[i] and remains increasing subsequence.

Let’s say LIS[i] represent longest increasing subsequence till i.

LIS[i] = 1 + MAX(LIS[j]) for j = 0 to i-1 and A[j] < A[i]

Implementation wise, checking every element from start of the array to element under consideration, if A[j] is less than A[i], then A[i] can be part of the subsequence ending with  A[i]. So length of longest increasing sub sequence can be MAX of (length of sub sequence ending at j )+1.

Let’s work out an example. Array A = [2,4,6,3,5,7,9]

Initialize LIS[0] = 1, there is increasing subsequence of length 1 at index 0.

For i = 1, j will range from index 0 to 0. a[0] < a[1], hence LIS[1]=2 (MAX(LIS[0]) + 1 ).

For i = 2, j will vary from 0 to 1. Get max of LIS[0] and LIS[1] and 1 to it. MAX LIS till index 1 is 2. Hence, LIS[2] = 3 ( LIS[1] +1 )

For i = 3, j ranges from 0 to 2, Max LIS till index 3 will be LIS[3] = 2 because only a[0] is less than a[3]. Hence, longest subsequence till index 3 will have length as 2. LIS[3] = 2.

For i = 4, i.e.5; LIS[4] Max ( LIS[0], LIS[1], LIS[3] ) + 1  = 3, sequence may be [ 2,4,5 ] or [ 2,3,5 ]

For i = 5, LIS[5] = Max (LIS[0], LIS[1], LIS[2], LIS[3], LIS[4]) + 1 = 4; subsequence may be [ 2,4,5,7] or [ 2,3,5,7 ] or [ 2,4,6,7 ]

For i = 6, LIS[6] = Max (LIS[0], LIS[1], LIS[2], LIS[3], LIS[4], LIS[5]) + 1 = 5;  [ 2,4,5,7,9 ] or [ 2,3,5,7,9 ] or [ 2,4,6,7,9 ] being possible longest subsequence till index 6.

Find longest increasing subsequence (LIS)


#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) {
	// your code goes here
	int a[] = { 2,4,6,3,5,7,9 };
	int size = sizeof(a)/sizeof(a[0]);
 
	printf("Length of Longest increasing subsequence : %d",
                                      lis(a, size));
 
	return 0;
}

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

There are many problems which are solved using finding longest increasing subsequence method. For example:
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.

Coming back to problem of longest increasing subsequence, complexity of brute force solution is exponential where as for dynamic programming approach is O(n2). Question is can we find longest increasing subsequence in nlogn complexity?

Longest increasing subsequence in nlogn)

Basic idea behind solution is to keep track of all active subsequences at a given point of time. Based on the current elements being consider, update these active lists. To understand this process, let’s work out an example.

A = {2,8,7}
Monotonically increasing subsequences are {2,8} and {2,7}

What if we add another element, 11 in this?

A = {2,8,7,11}
Monotonically increasing subsequences are {2,8,11} and {2,7,11}

What if new element 9 is added to array? What happens now? If we add it t0 subsequences, length of longest subsequence remains 3.

A = {2,8,7,11,9}
Monotonically increasing subsequences are {2,8,9} and {2,7,9}

Question is should we create new active subsequences with length 3 adding 9 to them or continue with 11 in them? Consider the next element is 10. At this point we know, that adding 9 to subsequence leads us to longer subsequences than keeping 11.

How do we decide when to replace and when to continue with the old element in subsequence?  We can add or replace current element A[i] to an existing sequence if there is an element A[j] (j > i) such that E < A[i] < A[j] or (E > A[i] < A[j] – for replace), E being the last element in subsequence. In above example, E = 11, A[i] = 9 and A[j] = 10.

What if A[i] is smaller than all elements in all subsequences? In this case, we have to create a new list and add A[i] into it. Whole idea is to maintain lists of increasing sequences and update them based  on new element.  Every time new element is to be added, scan all lists (for end elements) in decreasing order of their length. Below algorithm gives how to add, replace new element in existing list or to create a new list with it.

Longest increasing subsequence algorithm 

1. If A[i] is smallest among all end candidates of active lists, start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, clone the largest active list, and extend it by A[i].
3. If A[i] is in between, find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. 
4. Discard all other lists of same length as that of this modified list.

Longest increasing subsequence example

Let’s take an example and see how it works:
A = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13 ].

A[0] = 0. Case 1. Since there are no active lists, create a new one.
Lists = [[0]].

A[1] = 8. Case 2. A[i] is greater than end elements of al lists, so select the longest one and clone it extend.
Lists [ [0], [0, 8]

A[2] = 4. A[i] is less than end of one of the list and greater than other. Find the list which has end element less than A[i], it’s [0]. Clone it, extend and discard all list with similar length lists.
List = [ [0], [0, 4] ].
[0, 8] is discarded

A[3] = 12. Same as A[1].
Lists = [ [0], [0, 4], [0, 4, 12] ]

A[4] = 2. Same as A[2], Clone the one with largest end which is less than A[i], extend it and discard all same length lists.
Lists = [ [0], [0, 2], [0,4,12]
[0, 4] is discarded.

A[5] = 10. Same as A[4]. Clone, extend and discard.
Lists = [ [0], [0, 2], [0,4,10] ]
[0, 4, 12] is discarded.

A[6] = 6. Same as A[5] Clone, extend and discard.
Lists = [ [0], [0, 2], [0,2,6] ]
[0, 4, 10] is discarded.

A[7] = 14. Same as A[1]. Clone and extend.
Lists = [ [0], [0, 2], [0,2,6],  [0,2,6,14] ]

A[8] = 1. Same as A[6]. Clone, extend and discard.
Lists = [ [0], [0,1], [0,2,6] [0,2,6,14]
[0, 2] is discarded

A[9] = 9. Same A[8]. Clone, extend and discard.
Lists = [ [0], [0,1], [0,2,6] [0,2,6,9] ].
[ 0, 2, 6, 14 ] is discarded.

A[10] = 5. Same as A[9]. Clone, extend and discard.
Lists = [ [0], [0,1], [0,2,5] [0,2,6,9]].
[ 0, 2, 6] is discarded.

A[11] = 13. Same as A[1]. Clone and extend.
Lists = [ [0], [0,1], [0,2,5] [0,2,6,9], [0,2,6,9,13]].

LIS is [ 0,2,6,9,13] with length of 5.

This looks like lot of things to be done just for maintaining list and there requires a lot of space to store all of these lists. There is an insight which helps do optimize all this stuff, observer that all we are using from lists are their end elements. We do not care what was prior to them in list. So, can we store just end elements of an auxiliary array and do operations on them? Size of this array in worst case will be n if arrays is sorted.

To extend the list, add another element in auxiliary array. To replace just overwrite the smallest element which is greater than current element. To find smallest element which is greater than current element, we use algorithm called ‘Ceiling’, which is modification of binary search.

To find length of longest subsequence, keep track of length of auxiliary array, because at the end, length of it will be length of LIS.

Implementation of longest increasing subsequence in nlogn

#include<stdio.h>
#include<stdlib.h>
 
int ceilElement(int a[],int start,int end,int key){
	while(end-start > 1){
		int mid = start +(end - start)/2;
		if(a[mid]>=key){
			end = mid;
		}
		else{
			start = mid;
		}
	}
	return end;
}
 
int longestIncreasingSubsequence(int input[], int size)
{
	if(!size)
		return 0;
 
	int a[size];
	int length=1;
 
	a[0] = input[0];
 
	for(int i=1; i<size; i++)
	{
	    if(input[i]< a[0])
		    a[0]=input[i];
	    else if(input[i]>a[length-1])
		    a[length++]=input[i];
	    else
		    a[ ceilElement(a,-1,length-1,input[i]) ]= input[i];
	}
	return length;
}
 
int main() {
	int a[]={0,8,4,12,2,10,6,14,1,9,5,13,1,7,15};
	int size =sizeof(a)/sizeof(a[0]);
 
	printf("Longest Increasing Sub-sequence is = %d",
                                 longestIncreasingSubsequence(a,size));
	return 0;
}

Complexity of algorithm to find longest increasing subsequence in nlogn is of course O(n log n) as for each element in array, it requires log n time to find ceiling of it and put it at correct position.

This article is influence by http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn and comments provided by readers under these articles.

Please share if there is something missing or wrong in this article. We would love to correct it. Also, if you want to contribute and earn, please drop us a mail using contact us form.