# Longest increasing subsequence (Dynamic Programming)

I have written the following recursive structure for finding length of longest increasing subsequence.

int lis(int arr[],int n,int k,int prev)  //k=0 (pointing to start)
{                                   //prev=0 (value of prev element included in subsequence)
if(k==n)    return 0;
int res;
if(arr[k]>=prev)   res=max(1+lis(arr,n,k+1,arr[k]),lis(arr,n,k+1,prev));
else               res=lis(arr,n,k+1,prev);
return res;
}


1.So, firstly I check whether that element is greater than prev element or not. If it is greater then there are two recursive calls-

a) In first call that element is included and I send that element as prev in the next call and

b) in second call that element is not included in the subsequence.

2.If it is less than prev element than I simply don't include that element and proceed further.

I am trying to write the top-down approach (DP) for this. It cannot be written using 1-d array because it depends on value of k and previous values in the subsequence. How can I write the top to down approach for this?

I read an article on lis on GeeksForGeeks and found a different recursive structure for this problem.

But, I want to know that Can every recursive solution be written into top-down approach (DP) or do I have to find recursive solution (there can be more than one recursive solutions for a problem I think..) such that it follows optimal substructure property?

• Use a 2D array. Memoize. See cs.stackexchange.com/q/2644/755. – D.W. May 25 '18 at 22:39
• Thanks.. I solved it.. Should I delete this question?@D.W. – shiwang May 26 '18 at 7:43
• @DW Shiwang asking to delete this question. – kelalaka Oct 30 '18 at 20:24