Longest Increasing Subsequence

Hello Everyone,

Let us discuss the Longest Increasing Subsequence (LIS) problem as an example problem that can be solved using Dynamic Programming.
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Examples:

Input: arr[] = {3, 10, 2, 1, 20} Output: Length of LIS = 3 The longest increasing subsequence is 3, 10, 20 Input: arr[] = {3, 2} Output: Length of LIS = 1 The longest increasing subsequences are {3} and {2} Input: arr[] = {50, 3, 10, 7, 40, 80} Output: Length of LIS = 4 The longest increasing subsequence is {3, 7, 40, 80}

Method : Dynamic Programming.

We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.
The simulation of approach will make things clear:

Input : arr[] = {3, 10, 2, 11} LIS[] = {1, 1, 1, 1} (initially)

Iteration-wise simulation :

  1. arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2}
  2. arr[3] < arr[1] {No change}
  3. arr[3] < arr[2] {No change}
  4. arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2}
  5. arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3}
  6. arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3}

We can avoid recomputation of subproblems by using tabulation as shown in the below code:
Below is the implementation of the above approach:

/* Dynamic Programming C++ implementation

of LIS problem */

#include <bits/stdc++.h>

using namespace std;

/* lis() returns the length of the longest

increasing subsequence in arr[] of size n */

int lis( int arr[], int n)

{

int lis[n];

lis[0] = 1;

/* Compute optimized LIS values in

bottom up manner */

for ( int i = 1; i < n; i++) {

lis[i] = 1;

for ( int j = 0; j < i; j++)

if (arr[i] > arr[j] && lis[i] < lis[j] + 1)

lis[i] = lis[j] + 1;

}

// Return maximum value in lis[]

return *max_element(lis, lis + n);

}

/* Driver program to test above function */

int main()

{

int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

int n = sizeof (arr) / sizeof (arr[0]);

printf ( "Length of lis is %d\n" , lis(arr, n));

return 0;

}

Output

Length of lis is 5

Output:

Length of lis is 5

Complexity Analysis:

  • Time Complexity: O(n2).
    As nested loop is used.
  • Auxiliary Space: O(n).
    Use of any array to store LIS values at each index.

Note: The time complexity of the above Dynamic Programming (DP) solution is O(n^2) and there is a O(N log N) solution for the LIS problem. We have not discussed the O(N log N) solution here as the purpose of this post is to explain Dynamic Programming with a simple example. See below post for O(N log N) solution.