Longest Increasing Subsequence using Dynamic Programming

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.


 
For example, consider below subsequence
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Longest increasing subsequence is
0, 2, 6, 9, 11, 15

This subsequence has length 6; the input sequence has no 7-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15 or
0, 4, 6, 9, 13, 15

are other increasing subsequences of equal length in the same input sequence.

 


 

The idea is to use recursion to solve this problem. For each item, there are two possibilities –
 

1. We include current item in LIS if it is greater than the previous element in LIS and recurse for remaining items.
 
2. We exclude current item from LIS and recurse for remaining items.
 

Finally, we return maximum value we get by including or excluding current item. The base case of the recursion would be when no items are left.

 
C++ implementation –
 

Download   Run Code

Output:

Length of LIS is 6

 
The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

 


 

The problem has an optimal substructure. That means the problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler, smaller subproblems until the solution becomes trivial. Above solution also exhibits overlapping subproblems. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by using Dynamic Programming, in which subproblem solutions are Memoized rather than computed again and again. The Memoized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes L[i], for each 0 <= i < n, which stores the length of the longest increasing subsequence of subarray arr[0..i] that ends with arr[i]. To calculate L[i], we consider LIS of all smaller values of i (say j) already computed and pick the maximum L[j] where arr[j] is less than the current element arr[i]. It has the same asymptotic run-time as Memoization but no recursion overhead.

 
C++ implementation –
 

Download   Run Code

Output:

Length of LIS is 6

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n).

 


 

How to print LIS?

Above solutions only print the length of LIS but do not actually print LIS itself. To print the LIS, we actually have to store the longest increasing subsequence in lookup table instead of storing just LIS length.

For example consider

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

 
The Longest Increasing Subsequence of subarray arr[0..i] that ends with arr[i] are –


LIS[0] – 0
LIS[1] – 0 8
LIS[2] – 0 4
LIS[3] – 0 8 12
LIS[4] – 0 2
LIS[5] – 0 8 10
LIS[6] – 0 4 6
LIS[7] – 0 8 12 14
LIS[8] – 0 1
LIS[9] – 0 4 6 9
LIS[10] – 0 4 5
LIS[11] – 0 4 6 9 13
LIS[12] – 0 2 3
LIS[13] – 0 4 6 9 11
LIS[14] – 0 4 6 7
LIS[15] – 0 4 6 9 13 15

 
C++ implementation –
 

Download   Run Code

Output:

0 4 6 9 13 15

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

We will soon be discussing O(nlogn) algorithm to find length of Longest increasing subsequence.
 

References:
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
Dynamic Programming #1: Longest Increasing Subsequence
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz