hackersarkar12's blog

By hackersarkar12, history, 4 years ago, In English

I tried to solve longest increasing subsequence in top down but only pass few cases i don't know whether it is full right or wrong here is the code which i tried

this question is from leetcode

int lis(vector<int>&nums,int i,int n,int prev,vector<int>& ls){
if(i==n||n==0){
    return 0;
}
if(ls[i]!=-1){
    return 1 ;
 }


   lis(nums,i+1,n,prev,ls);
   if(nums[i]>prev){
     int  num=1+lis(nums,i+1,n,nums[i],ls);

       ls[num]=1;
      return num;
     }
    return 0;
      }





      class Solution {
    public:
      int lengthOfLIS(vector<int>& nums) {
         int  n=nums.size();
          int c;
         vector<int> ls(n+1,-1);

       lis(nums,0,n,INT_MIN,ls);
      for(int i=n;i>=0;i--){
         if(ls[i]!=-1){
           c=i;
             break;
         }
         else{
           c=0;
         }
       }
        if(nums.size()==0){
        return 0;
          }
         else{

       if(c==0){
     return 0;

     }
   else{
   return c;
    } 

     }



         }



       };

I wants to how to write top-down approach of this question and wants to know the solution of this question in c++ can anyone explain me ?

  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?