Dynamic Programming : Longest increasing sub sequence in an array

Longest increasing subsequence problem

Given an array of integers, find the largest sub sequence such that if i<j then a[i] <a[j].
For example, in array {2,4,6,3,5,7,9} longest increasing sub sequence is of length 5 {2,4,6,7,9}

Analysis

Here idea is to find out if  the longest subsequence already present before a particular element can include this element and remains increasing after adding this element. This can be easily done by checking every element from start of the array to element under consideration, if element i is less than current element, then current element can be part of the sub sequence ending with element i. So length of longest increasing sub sequence can be (length of sub sequence ending at i )+1. We would check for each such element and take the maximum length.

Let’s work on an example.

A = {2,4,6,3,5,7,9}

Now we initialize len[0] =1, that means there is an increasing sub sequence of length 1 at index 0.

for i =1 i.e 4, we will check 0 to 1. We start with 0, a[0] < a[1], hence LIS length is 2 (LIS[0] +1).

For i =2, i.e. 6 we check 0 to 2.   We check that LIS[0] =1 and LIS[1] =2. We can have a sub sequence ending a[1] and adding a[2]. Hence max LIS is 3 till index 2. Hence LIS[2] = 3 (LIS[1] +1).

For i =3 i.e 3, we 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 sub sequence ending with a[3] will have length only of 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}

There are many problems which can be solved by finding longest increasing subsequence. 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. 

Code to find longest increasing subsequence

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

Dynamic Programming : Find the longest palindrome string

Find longest palindrome substring in string

We can easily find longest palindrome in a string using brute force. Idea is to start from each character in the string and go on checking on the left and right side of the character till the time they are same. Once they differ, we check if the number of characters in string centered character is greater than earlier such string for any character processed earlier. If it is greater, then we update the longest palindrome substring length and look for subsequent characters till the end of the string.

Pseudo Code for brute force algorithm

Repeat all steps in above Pseudo code, starting with 1 for i (not with zero). (For taking into account even length string).

Code

Complexity of the above code is O(N^2).

Dynamic Programming approach

Can we do better than this?  Dynamic programming comes into picture. 
To understand dynamic, one simple example which comes in mind.
Let’s say somebody wants you to count match sticks on the floor. You count it and report that there are 8 such match sticks on floor. Other person throws one more stick and asks you same question again. What do you do? You don’t count all sticks again. You just reuse the information gained in first step to come up with answer for the second question.
Similarly, when answer to sub-problems are used to solve a bigger problem, is called as dynamic programming.
In following problems and problem in subsequent posts, we would see that we have same underlying principle in all solutions.
Let’s analysis the problem at hand that is to find longest palindrome substring.
We know that every character in itself is a palindrome string. So we can safely say that 
Again, a string with two characters is palindrome if both characters are equal.
Can we build on top of this?
Now for every string length greater than 2, we would find the string of that length starting with every index in it.  Now we would consider the first and last character in the string of length L.
If the characters are equal, we can add 2 to the length of sub-string with length L-2
Here i represent the start of the string, and j end of the string.
So palin(i,j) represents the max length of palindrome in string L, with starting index as i and end index as j.
If the characters are not same, then we can update the length by including one of the character whichever gives the max value.
So we fill the table starting from (0,0) to (n,n) and palin(0,n) is longest palindrome substring length in given string gives us the answer. 🙂 

Code for longest palindrome substring

Complexity of dynamic programming approach is much better than brute force algorithm and is O(N *N), It used extra memory though in order O(N*N).