What's wrong here..any suggestions.


  • 0
    L

    I tried both implementations of DP and memo, but somehow I am seing an error and TLE error.
    Any suggestion what is missing.

    vector<int> mem;
    int lis(vector<int> &nums, int p)
    {
        if(nums.size() == 0 ) return 0;
        
        int tab[nums.size()] ={0};
        
        tab[0]=1;
        
        for(int p= 1; p<nums.size(); p++)
            for(int i=p-1; i>=0; i--)
                if( nums[p] > nums[i])
                    tab[p]= max(tab[p], tab[i]+1);
                else    
                    tab[p]= max(tab[p], tab[i]);     
                
        
        return tab[nums.size()-1];
    }
    
    int lis_rec(vector<int> &nums, int p)
    {
        if( mem[p]!=-1)
            return mem[p];
    
        if(nums.size()-p <= 1)
                return mem[p]=nums.size()-p;
        int cmax=0;
        for( int i =p+1; i<nums.size();i++)
        {
            int leni= lis(nums, i);
            if( nums[p] < nums[i] )
                      leni= leni+1;
            cmax = max(leni, cmax);
        }
        return mem[p]=cmax;
    }
    
    int lengthOfLIS(vector<int>& nums) {
        if(!nums.size()) return 0;
        
        mem.resize(nums.size(),-1);
        return lis(nums,0);
    
    }

  • 0
    M
    int lis(vector<int> &nums, int p)
    {
        if(nums.size() == 0 ) return 0;
    
        int tab[nums.size()] ={0};
    
        tab[0]=1;
    
        for(int p= 1; p<nums.size(); p++)
            for(int i=p-1; i>=0; i--)
                if( nums[p] > nums[i])
                    tab[p]= max(tab[p], tab[i]+1);
                else    
                    tab[p]= max(tab[p], tab[i]);     
    
    
        return tab[nums.size()-1];
    }
    

    this is like the O(n^2) solution... but the logic is wrong here --

    if( nums[p] > nums[i])
        tab[p]= max(tab[p], tab[i]+1);
    else    
        tab[p]= max(tab[p], tab[i]); 
    

    if (nums[p] > nums[i]), tab[p] MIGHT BE 1+tab[i]; otherwise, tab[p] MIGHT BE 1 since nums[i]>=nums[p]. tab[p] is the largest among these MIGHT BE values.


  • 0
    L

    Could you kindly explain more since I could not understand where's the mistake.

    if( nums[p] > nums[i])
        tab[p]= max(tab[p], tab[i]+1);
    else    
        tab[p]= max(tab[p], 1); 

  • 0
    M

    This part should be right (though not concise). tab[p] is defined as "the length of the LIS ENDING WITH nums[p]", so return tab[nums.length-1] is not right, because you are returning the length of the LIS which ends with nums[nums.length-1], however, the real LIS is not necessarily ending with nums[nums.length-1]. What you should find is the maximum of tab[0...nums.length-1].


  • 0
    M
    public class Solution {
        public int lengthOfLIS(int[] nums) {
            if (nums==null || nums.length==0) { return 0; }
            int[] dp = new int[nums.length];
            dp[0] = 1;
            int globalMax = 1;
            for (int i=1; i<nums.length; ++i) {
                int localMax = 0;
                for (int j=0; j<i; ++j) {
                    if (nums[j] < nums[i]) { localMax = Math.max(localMax, dp[j]); }
                }
                globalMax = Math.max(globalMax, 1+localMax);
                dp[i] = 1 + localMax;
            }
            return globalMax;
        }
    }
    

    this is my O(n^2) code, hope it helps


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.