Longest increasing sub-sequence - Dynamic Programming

An increasing subsequence is a subset { a_i1,a_i2,...,a_ik } of a larger sequence of numbers { a₁, a₂, .... , a_n }, such that

(a) 1 <= i₁ < i_{2 <} .... < i_k <= n, and

(b) a_i1 < a_i2 < .... < a_ik.

A longest increasing subsequence is the largest among all the possible increasing subsequences.

For example, if the given sequence of numbers is :

{ 10, 4, 15, 12, 7, 12, 17, 14, 19, 5 },

The longest increasing subsequence is of length 5, which is:

{ 4, 7, 12, 17, 19 } and { 4, 7, 12, 14, 19 }

Method 1: Recursion

LIS_recur(list[], n) :

for i = 1 to n-1 :

lis = LIS_recur(list, i)

if (list[i] < list[n] and 1 + lis > max_Ending_at_n) :

max_Ending_at_n = lis + 1;

return (max of all values returned by various calls to LIS_recur(i))

The worst case running time of this simple approach is exponential, as it solves the same subproblems multiple times.

To understand this see the following illustration :

We see that just for 4 smallest subproblems, the recursive calls to the function is growing exponentially, and same problem is being solved again and again. Its not even possible to show the recursive calls for last element on a piece of A4 sheet.

Lets look at the recursive calls mathematically.

T(n) = T(n-1) + T(n-2) + …. + T(1) + 1

T(1) = 1 [ 2⁰ ]

T(2) = 1 + T(1) = 2 [ 2¹ ]

T(3) = 1 + T(1) + T(2) = 1 + 1 + 2 = 4 [ 2² ]

T(4) = 1 + 1 + 2 + 4 = 8 [ 2³ ]

T(5) = 1 + 1 + 2 + 4 + 8 = 16 [ 2⁴ ]

….................

T(n) = 2^n-1

// C++ code : LIS

/*

* LIS.cpp

*

* Created on: Feb 7, 2015

* Author: CodingTonic

*/

#include <iostream>

using namespace std;

// A simple recursive function to find the length of longest increasing subsequence

int lis_recur(int arr[], int n, int &maxRef)

{

    //cout << "lis_recur(" << arr[n-1] << ")" << endl;

    if(n==1)

        return 1;

    

    int len = 1;

    int currMax = 1;

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

        len = lis_recur(arr, i, maxRef);

        if((arr[i-1] < arr[n-1]) && (len + 1 > currMax)){

            currMax = len + 1;

        }

    }

    if(maxRef < currMax){

        maxRef = currMax;

    }

    return (currMax);

}

// the main function

int main(int argc, char *argv[])

{

    int arr[] = {10, 4, 15, 12, 7, 12, 17, 14, 19, 5};

    int max = 1;

    lis_recur(arr, sizeof(arr)/sizeof(arr[0]), max);

    cout << max << endl;    

    return (0);

}

Output: 5

Time Complexity: O(2ⁿ) 

Method 2: Dynamic Programming

The arrows in the above graph denote all the possible valid transitions. For all the edges e = (a,b), a &lt; b, and a occurs earlier in the original sequence.

Note: the above graph forms a DAG(directed acyclic graph), since all edges go in one direction. So, our aim is to find the longest path in the DAG.

Algo:

for j = 1 to n :

L(i) = 1 + max{ L(j) : (i, j) belongs to E }

return max_j L(j)

L(j) is the length of the longest path (longest increasing subsequence) ending at index j. We add 1 to it since, we are counting the nodes on the path an not the edges.

So, in order to solve our original problem, we have defined a collection of subproblems {L(j) : 1 &lt;= j &lt;= n }. There is an ordering on the subproblems, because in order to solve the problem we only need the solutions to smaller problems, solving which would solve the larger problem. This property allows us to solve solve it in a single pass.

/*

* LIS.cpp

*

* Created on: Feb 7, 2015

* Author: CodingTonic

*/

#include <iostream>

using namespace std;

// A dynamic-programming solution to find the longest increasing subsequence

int lis_DP(int arr[], int n)

{

    if(n==1)

        return 1;

    int len = 1;

    // allocate memory to store longest subsequence ending at each index

    int *LIS_arr = new int[n];

    // allocate memory to store the index of previous index in the subsequence ending at each index

    int *p = new int[n];

    int lis_endIndex = 0; // index of the last element of the l.i.s.

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

        LIS_arr[i] = 1;

        p[i] = -1;

    }

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

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

            if( (arr[j] < arr[i]) && (LIS_arr[i] < LIS_arr[j] + 1) ){

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

                p[i] = j;

            }

        }

    }

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

        if(LIS_arr[i] > len){

            len = LIS_arr[i];

            lis_endIndex = i;

        }

    }

    // print the longest increasing subsequence in reverse order

    while(lis_endIndex != -1){

        cout << arr[lis_endIndex] << " ";

        lis_endIndex = p[lis_endIndex];

    }

    cout << endl;

    // free the dynamically allocated memory for temporary arrays

    delete []LIS_arr;

    delete []p;

    // return the length of longest increasing subsequence

    return (len);

}

// the main function

int main(int argc, char *argv[])

{

    int arr[] = {10, 4, 15, 12, 7, 12, 17, 14, 19, 5};

    

    cout << lis_DP(arr, sizeof(arr)/sizeof(arr[0])) << endl;

    return (0);

}

Output: 

19  17  12  7  4  

5

Time Complexity: O(n²)




// C code:

/*

============================================================================

Name : lis.c

Author : CodingTonic

Version :

Copyright : CodingTonic

Description : longest increasing subsequence

============================================================================

*/

#include <stdio.h>

#include <stdlib.h>

// A dynamic-programming solution to find the longest increasing subsequence

int lis_DP(int arr[], int n)

{

  if(n==1)

  return 1;

  int len = 1;

  // allocate memory to store longest subsequence ending at each index

  int *LIS_arr = (int *)malloc(n*sizeof(int));

  // allocate memory to store the index of previous index in the subsequence ending at each index

  int *p = (int *)malloc(n*sizeof(int));

  int lis_endIndex = 0; // index of the last element of the l.i.s.

  int i, j;

  for(i=0; i<n; ++i){

    LIS_arr[i] = 1;

    p[i] = -1;

  }

  for(i=0; i<n; ++i){

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

      if( (arr[j] < arr[i]) && (LIS_arr[i] < LIS_arr[j] + 1) ){

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

        p[i] = j;

      }

    }

  }

  for(i=0; i<n; ++i){

    if(LIS_arr[i] > len){

      len = LIS_arr[i];

      lis_endIndex = i;

    }

  }

  // print the longest increasing subsequence in reverse order

  while(lis_endIndex != -1){

    printf("%d ",arr[lis_endIndex]);

    lis_endIndex = p[lis_endIndex];

  }

  printf("\n");

  // free the dynamically allocated memory for temporary arrays

  free(LIS_arr);

  free(p);

  // return the length of longest increasing subsequence

  return (len);

}

int main(void) {

  int arr[] = {10, 4, 15, 12, 7, 12, 17, 14, 19, 5};

  printf("%d",lis_DP(arr, sizeof(arr)/sizeof(arr[0])));

  return 0;

}

Output: 

19  17  12  7  4  

5