Implement LIS using recursion and top down dp efficiently.

How to implement LIS(Longest Increasing Subsequence) using recursion and top down dp efficiently?

There you go : http://stackoverflow.com/questions/37561909/does-there-exist-a-top-down-dynamic-programming-solution-for-longest-increasing

Dear @rashedcs

please follow the link (courtesy :- MIT OCW)

And here’s a problem and it’s successful submition

Problem link:- https://www.hackerrank.com/challenges/longest-increasing-subsequent

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

#define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])
// Binary search (note boundaries in the caller)
// A[] is ceilIndex in the caller
int CeilIndex(int A[], int l, int r, int key) {
int m;

while( r - l > 1 ) {
    m = l + (r - l)/2;
    (A[m] >= key ? r : l) = m; // ternary expression returns an l-value
}

return r;
} 

 int LongestIncreasingSubsequenceLength(int A[], int size) {
 // Add boundary case, when array size is one

int *tailTable   = new int[size];
int len; // always points empty slot

memset(tailTable, 0, sizeof(tailTable[0])*size);

tailTable[0] = A[0];
len = 1;
for( int i = 1; i < size; i++ ) {
    if( A[i] < tailTable[0] )
        // new smallest value
        tailTable[0] = A[i];
    else if( A[i] > tailTable[len-1] )
        // A[i] wants to extend largest subsequence
        tailTable[len++] = A[i];
    else
        // A[i] wants to be current end candidate of an existing subsequence
        // It will replace ceil value in tailTable
        tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];
}

delete[] tailTable;

return len;
}
int A[1000009]={0}; 
int main() {
int n,i;
cin>>n;
for(i=0;i<n;i++)
	cin>>A[i];	

printf("%d\n",LongestIncreasingSubsequenceLength(A, n));

return 0;
}

you need to learn to use your secret <ahref=“http://www.corriganandcompany.com/case-study-by-dr-devicharan-shetty-dc-shetty-on-reproducibility/”>Dr Devi Charan Shetty
Dr Devi Charan Shettyit