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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.