Home > Applied Algorithms, Arrays, Dynamic Programming > Longest Increasing Subsequence

Longest Increasing Subsequence

Problem Statement: You are given an array with integers (negative, positive, zero). You are supposed to find the length of the longest increasing subsequence in the array. The elements of the subsequence are not necessarily contiguous.

Once again, as in the last problem, you cannot afford to try a brute force method and be called an even bigger fool. What you can do is look at the problem carefully and find the optimal substructure. You can find the length of the longest increasing subsequence till each position and use this for the later positions.

The way it would work is, at each position ‘i’ in input array A, go through the positions j<i in array B and find the largest value for which A[i]>=A[j]. Now you put the value of B[i] = the value you found + 1.

Did you understand what we did? Since we are supposed to find the length of the longest increasing subsequence, we found the element smaller than this whose corresponding value in array B (length of longest increasing subsequence till that point) is the highest. This value + 1 would then be the length of the longest increasing subsequence till ‘i’.

For example, for the input array A as follows,

-1, 4, 5 ,-3, -2, 7, -11, 8, -2

We would get the array B as follows,

1, 2, 3, 1, 2, 4, 1, 5, 2

Once again, traversing this particular array B and finding the largest value would give us the length of the longest increasing subsequence. 🙂

If the solution isn’t apparent to anyone, please refer the video link, here,

http://people.csail.mit.edu/bdean/6.046/dp/ 

Task for you : Find the elements that form this longest increasing subsequence. Pretty easy. 🙂

PS: Many variations of this problem exist (strictly increasing, decreasing, strictly decreasing). Also, it is posed in different ways, some of which you can find at (http://www.uvatoolkit.com) by simply typing the phrase LIS as the search parameter. Enjoy! 🙂

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: