I tried to solve longest increasing subsequence in top down

Правка en1, от hackersarkar12, 2020-07-30 09:55:02

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&nums,int i,int n,int prev,vector& 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 ?

Теги c++ 14, #dynamic programing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский hackersarkar12 2020-07-30 09:55:58 16 Tiny change: 'code\n\n\nint lis(ve' -> 'code\n\n\n \n\n\n int lis(ve'
en1 Английский hackersarkar12 2020-07-30 09:55:02 1568 Initial revision (published)