**By: Saurav**

**2017-11-10 21:14:00 UTC**

Find the longest increasing subsequence of a given sequence / array.

In other words, find a subsequence of array in which the subsequenceâ€™s elements are in strictly increasing order, and in which the subsequence is as long as possible.

This subsequence is not necessarily contiguous, or unique.

In this case, we only care about the length of the longest increasing subsequence.

Example :

Input : [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Output : 6

The sequence : [0, 2, 6, 9, 13, 15] or [0, 4, 6, 9, 11, 15] or [0, 4, 6, 9, 13, 15]

InterviewBit

This is an interesting one!

We need to use dynamic programming to solve this problem.

Since we need increasing sub sequence which may not be contiguous, we need to keep track of the increasing sub sequence of elements till that element and then decide for the current one if its increasing or not.

Figure below help us visualize this.

A great tutorial is available by Tushar Roy

As in the figure above, we start by analyzing maximum length of the sub sequence of an array of length 1: [5]

Then we analyze for array of two elements: [5,7] and store the result in another array.

We do this process again and again for all the elements in the given array and put the maximum number in a final_array.

The algorithm is:

**1st Attempt**

Not so great! Lets work on it a little and make it cleaner, and let function do just one thing.

**Attempt 2:**

All our tests pass and the code looks clean but its still a O(n^2) solution.

I will update the post after working on a more efficient solution.

Let me know what you think!

twitter: sprakash24oct

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)