[LIS] Longest Increasing Subsequence

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. For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

On2

http://algorithms.tutorialhorizon.com/dynamic-programming-longest-increasing-subsequence/

http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/



OnLogn

http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/



Variations of LIS:

http://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/

http://algorithms.tutorialhorizon.com/dynamic-programming-box-stacking-problem/



Method 1:Recursion

int _lis( int arr[], int n, int *max_ref)

{

  

    if(n == 1)

        return 1;



    int res, max_ending_here = 1; // length of LIS ending with arr[n-1]



    /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If

       arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs

       to be updated, then update it */

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

    {

        res = _lis(arr, i, max_ref);

        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)

            max_ending_here = res + 1;

    }



    /* Compare max_ending_here with the overall max. And update the

     overall max if needed  */

    if (*max_ref < max_ending_here)

       *max_ref = max_ending_here;



    // Return length of LIS ending with arr[n-1]

    return max_ending_here;

}



int lis(int arr[], int n)

{

    // The max variable holds the result

    int max = 1;



    _lis( arr, n, &max );



    // returns max

    return max;

}



Method 2:Dynamic Programming with O(n2)--Returns only Length



#include <iostream> #include<string.h> using namespace std; int lis( int arr[], int n ) {    int *lis, i, j, max = 0, k=1;    lis = (int*) malloc ( sizeof( int ) * n );    for ( i = 0; i < n; i++ )       lis[i] = 1;        for ( i = 1; i < n; i++ )       for ( j = 0; j < i; j++ )          if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)             lis[i] = lis[j] + 1;        for ( i = 0; i < n; i++ )       if ( max < lis[i] )          max = lis[i];              //For printing the LIS        for (i=0;i < n ; i++)      {   if(lis[i]==k)           { cout << arr[i] << endl;             k++;           }                 }              free( lis );    return max; } int main(){     int a[]={10,22,9,33,21,50,41,60,80};     int n=sizeof(a)/sizeof(a[0]);     cout << "The lis value is "<< lis(a,n )<< endl;     system("pause");     return 0; }



Note: In order to calculate the subsequence backtrack from the position of LIS and pick the element whose value is 1 less than the place you came from.



Method 3:Dynamic Programming with O(nlogn)





Method 4:Using LCS-O(n2)