Longest increasing subsequence – The Coding Interview Blog

Question 56. Find the longest increasing subsequence in an unsorted array of numbers

Consider the sequence A = {30, 40, 20, 70, 10}. The longest increasing subsequence is {30, 40, 70}. Here we are considering a strictly increasing longest subsequence and so a number can be present only once in the longest increasing subsequence even if it occurs several times in the original sequence. To solve the problem, we use dynamic programming as follows:

1.) We make use of an array called seq_length where seq_length[i] stores the length of the longest increasing subsequence ending at the position i. For instance seq_length[3] stores the length of longest subsequence from 0th to 3rd position, i.e. for the region {30, 40, 20, 70} in the above example. We initialize seq_length array with 1 at each position since each number itself forms a sequence of size 1 by itself.

2. We then compute the seq_length[i] from position 1 onwards using the formula:
seq_length[i] = 1 + max(seq_length[j]) where j < i and A[j] < A[i]

3. Once we have computed sequence lengths for all positions, then the maximum value in the seq_length array gives the length of the longest increasing subsequence. In our example, the maximum value in the seq_length array is 3. So length of longest increasing subsequence is 3.

The time complexity of this approach is O(n²).

C/C++


/*
a: array in which we need to find the longest increasing sequence
n: number of elements in the array. Should be >= 1
lis: the longest increasing sequence is returned in this array
Return value: length of the longest increasing sequence
*/
int find_lis(int a[], int n, int lis[])
{
	/*seq_length stores length of LIS for each position of array a*/
	int *seq_length = (int*) calloc(n, sizeof(int));

	/*prev_ix stores the index of previous element in the LIS sequence*/
	int *prev_ix = (int*) calloc(n, sizeof(int));

	int i, j, lis_length, lis_end;

	/*Each element by itself forms a sequence of length 1*/
	for (i = 0; i < n; ++i)
		seq_length[i] = 1;

	/*Find the LIS for each position in array a*/
	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {
			if ( a[j] < a[i] && seq_length[i] < seq_length[j] + 1 ) {
				seq_length[i] = seq_length[j] + 1;
				prev_ix[i] = j;
			}
		}
	}

	/*The longest LIS amongst all positions of array a will be the LIS  
	for the whole array*/
	lis_length = 1;
	lis_end = 0;
	for (i = 1; i < n; ++i) {
		if (lis_length < seq_length[i]) {
			lis_length = seq_length[i];
			lis_end = i;
		}
	}

	/*Use the prev_ix array to reconstruct the LIS for the whole array
	lis_end has the index of the last element in the LIS for whole array*/
	j = lis_end;
	for (i = lis_length - 1; i >= 0; --i) {
		lis[i] = a[j];
		j = prev_ix[j];
	}
	
	free(seq_length);
	free(prev_ix);

	return lis_length;
}

Java


/*a: array in which we need to find the longest increasing sequence.
	Should have atleast 1 element
Return value: array having the longest increasing sequence is returned
*/
public static int[] findLis(int[] a) {
	int n = a.length;

	/*seqLength stores length of LIS for each position of array a*/
	int[] seqLength = new int[n];

	/*prevIx stores the index of previous element in the LIS sequence*/
	int[] prevIx = new int[n];


	/*Each element by itself forms a sequence of length 1*/
	int i, j;
	for (i = 0; i < n; ++i)
		seqLength[i] = 1;

	/*Find the LIS for each position in array a*/
	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {
			if ( a[j] < a[i] && seqLength[i] < seqLength[j] + 1 ) {
				seqLength[i] = seqLength[j] + 1;
				prevIx[i] = j;
			}
		}
	}

	/*The longest LIS amongst all positions of array a will be the LIS
	for the whole array*/
	int lisLength = 1;
	int lisEnd = 0;
	for (i = 1; i < n; ++i) {
		if (lisLength < seqLength[i]) {
			lisLength = seqLength[i];
			lisEnd = i;
		}
	}

	
	int[] lis = new int[lisLength]; 

	/*Use the prevIx array to reconstruct the LIS for the whole array
	lisEnd has the index of the last element in the LIS for whole array*/
	j = lisEnd;
	for (i = lisLength - 1; i >= 0; --i) {
		lis[i] = a[j];
		j = prevIx[j];
	}

	return lis;
}

Python


#a: list in which we need to find the longest increasing sequence
#	should have at least 1 element
#Return value: list having the longest increasing sequence is returned
def find_lis(a) :
	n = len(a)

	#seq_length stores length of LIS for each position of list a
	#Each element by itself forms a sequence of length 1
	seq_length = [1 for i in range(0, n)]

	#prev_ix stores the index of previous element in the LIS sequence
	prev_ix = [0] * n

	#Find the LIS for each position in list a
	for  i in range(1, n):
		for  j in range(0, i):
			if ( a[j] < a[i] and seq_length[i] < seq_length[j] + 1 ) :
				seq_length[i] = seq_length[j] + 1
				prev_ix[i] = j
			
	#The longest LIS amongst all positions of list a will be the LIS 
	#for the whole list 
	lis_length = 1
	lis_end = 0
	for  i in range(1, n):
		if (lis_length < seq_length[i]) :
			lis_length = seq_length[i]
			lis_end = i
		
	lis = [0] * lis_length

	#Use the prev_ix list to reconstruct the LIS for the whole list
	#lis_end has the index of the last element in the LIS for whole list
	j = lis_end
	for  i in range(lis_length - 1, -1,-1):
		lis[i] = a[j]
		j = prev_ix[j]
	
	return lis