Longest Increasing Subsequence

LIS.cpp

int LIS(int arr[],int n){
    //base case 
    if(n==1) return 1;
    //otherwise 
    int curr_max=1;

    for(int i=0;i<n-1;++i){ // i< n-1 because n>=2
        while(arr[i]<arr[n-1] ){
          int subproblem=LIS(arr,i);
          if( (subproblem+1 >curr_max)  )
              curr_max=1+subproblem;
        }//while ends
    }//for ends 
    return curr_max;
}

LIS.py

def LIS(arr,n):
  

    if n==1:#base case 
        return 1
    curr_max=1

    for i in range(0,n-1):   
        subproblem=LIS(arr,i)
        if arr[i]<arr[n-1] and \
            curr_max < (subproblem +1 ):
            curr_max=1 + subproblem 

    # to this point ,we have already found the answer
    return curr_max   



# Driver program to test the functions above
def main():
	arr = [10, 22, 9, 33, 21, 50, 41, 60]
	n = len(arr)
	print ("Length of LIS is", LIS(arr, n))

if __name__=="__main__":
	main()

tabulatedLIS.cpp

/* Dynamic Programming C/C++ implementation of LIS problem */
#include<stdio.h>
#include<stdlib.h>
 
/* lis() returns the length of the longest increasing
  subsequence in arr[] of size n */
int lis( int arr[], int n )
{
    int *lis, i, j, max = 0;
    lis = (int*) malloc ( sizeof( int ) * n );
 
    /* Initialize LIS values for all indexes */
    for (i = 0; i < n; i++ )
        lis[i] = 1;
 
    /* Compute optimized LIS values in bottom up manner */
    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;
 
    /* Pick maximum of all LIS values */
    for (i = 0; i < n; i++ )
        if (max < lis[i])
            max = lis[i];
 
    /* Free memory to avoid memory leak */
    free(lis);
 
    return max;
}
 
/* 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;
}

tabulatedLIS.py

def LIS(arr,n):
    lis=[1]*len(arr)
    #initialize 
    for x in lis:
        x=1
    #compute optimal 
    for i in range(1,n):
        for j in range(0,i-1):
            if arr[i]>arr[j] and \
                (lis[i]<lis[j]+1):
                lis[i]=lis[j]+1
    #pick maximum of all LIS values

    return max( lis )