DP: Longest Increasing Subsequence

So this article will basically walk you through how to solve another classic DP problem , this algorithm is basically a dynamic programming based algorithm. Now the question is “What is Dynamic Programming” so in basic terms we can define Dynamic Programming as optimization over recursion or plain recursion. So whenever we see a recursion based solution or algorithm which has repeated calls for same inputs, we can optimize it using Dynamic Programming.Two basic tactics involved in DP are:-

Tabulation: Bottom Up approach

Memoization: Top Down approach

Steps involved in Dynamic Programming

• Define subproblems to the original problem.

• You find solution to the sub-problems

• You relate all sub-problems and store the result (memoization).

• You recurse and use the memoized table.

• You build a solution to the original problem via bottom-up and memoized table.

Now we will talk about our algorithm that is the Longest Increasing Subsequence algorithm we will discuss this algorithm as a problem which can be solved using dynamic programming. The LIS(Longest Increasing Subsequence) algorithm is used to find the length of the longest subsequence of a given sequence so that all the elements of the subsequence are sorted in increasing order. This algorithm can be implemented in many ways like using brute force approach, dynamic programming and more.

Methods/Approach to solve our problem:

Approach1: RECURSION(Brute Force)

Let arr[0 to n-1] be the input array and let l(i) be length of LIS at index I, arr[i] be the last element of the LIS.

Then, l(i) can be recursively written as:

l(i) = 1 + max( l(j) ) where 0 < j < i and arr[j] < arr[i]; or

l(i) = 1, if no such j exists.

Now the length of the LIS ending at i(index), will be 1 more than the max(lenght) of all the increaisng subsequences which are ending at indices before i, and where the following condition is true => arr[j] < arr[i] (j < i) from this we can easily see that our LIS problem can be solved using solutions to subproblems. The recursive tree given below will make the approach clearer:

Example:

Code:

Time Complexity and Auxiliary Space:

This brute force i.e recursive approach gives us an exponential time solution since there is a case of overlapping subproblems as explained in the recursive tree diagram shown above. So this approach is too slow for any big size sequence like if the array has 500 elements then time complexity becomes 2⁵⁰⁰ = 1125899906842624 which is very high so this approach takes a lot of time therefore making it inefficient so this is not an ideal solution to the given problem and we can solve it in less time using the dynamic programming approach. No external space used for storing values apart from the internal stack space.

Approach2: Dynamic Programming

So what was the main problem in the above approach that is the brute force approach was that there were many subproblems and we had to calculate the result again and again in each step in the above recursive solution . So this algorithm has Overlapping Substructure property and enumeration of same subproblems can be avoided by either using Memoization or Tabulation.

Let us Draw the tree again for the recursion used in the brute force approach:

So we can see that there are overlapping subproblems and also holds an optimal substructure property. We can find from the tree drawn above that the time complexity becomes exponential so by using the dynamic programming method we can improve the time complexity since the implementation of the dynamic programming approach is bottom-up.

What are the other elements or aspects which we should keep in mind of dynamic programming that we need to figure out?

1.) There is only one parameter or constraint on which the state of the problem depends which is the size of the array we are considering it to be N in our example.

2.) Now we need to store the solution of the subproblems as we are using memorization which uses bottom-up approach, therefore we need to define the table structure and table size. The table structure is influenced by the number of problem variables. In our case we consider it as 1 therefore we need a single dimensional array only to store the solution or results. The size of the table is dependent on the num. of subproblems suppose there are ’N’ subproblems, each index forms a subproblem of finding the LIS at that index.

3.) Intialising the table: arr[0] = 1;

4.) We can create or make the the iterative structure to fill the table by using this recurrence relation:

5.) So after we have filled the table in bottom-up manner, we have the LIS ending at each index. Now we iterate the auxiliary array to find the maximum number which will give us the desired result from the given array.

Pseudo-Code

You can find full implementation here.

Now let me give you a Iteration-wise simulation for better understanding of the approach.

Let us consider a array: A[] = {3, 10, 2, 11} and let us define a second array for our LIS that is

L[] = {1, 1, 1, 1} (initially)

Iteration-wise simulation :

1. If(A[2] > A[1])

{LIS[2] = max(LIS [2], LIS[1]+1)=2};

2. If(A[3] < A[1])

{No change}

3. If(A[3] < A[2])

{No change}

4. If(A[4] > A[1])

{LIS[4] = max(LIS [4], LIS[1]+1)=2}

5. If(A[4] > A[2])

{LIS[4] = max(LIS [4], LIS[2]+1)=3}

6. if(A[4] > A[3])

{LIS[4] = max(LIS [4], LIS[3]+1)=3}

Analysis

Now for the above algorithm that is the brute force(recursive) approach we found out that it gives us a exponential solution so using this method we get T(n) = O(n²) since nested loop is used. Now there is another approach which can further reduce the time complexity to O(nLogn) but we will not be covering that method in this article since our main aim was to explain the dynamic programming approach.

Sources:

1. ) Dynamic Programming (https://www.geeksforgeeks.org/dynamic-programming/).
2. ) Demystifying Dynamic Programming (https://medium.com/free-code-camp/demystifying-dynamic-programming-3efafb8d4296).