Is this O(n)? Is the logic correct?


  • 0
    S

    public class Solution
    {

    public int lengthOfLIS(int[] nums) 
    {
        if(nums.length==0) 
            return 0;
        
        return length(0, nums.length, nums);
    }
    
    public int length(int start, int end, int[] nums)
    {
        int trackmax = nums[0], trackmin = nums[0];
        int length =1;
        for(int i=start+1; i<end; i++)
        {
            if(nums[i] > trackmax)
            {
                length++;
                trackmax = Math.max(trackmax, nums[i]);
                trackmin = Math.min(trackmin, nums[i]);
            }
            else
            {
                    if(nums[i]< trackmin)
                    {
                        int templen=length(0, i, nums);
                        
                        length= Math.max(length, templen);
                    }
            }
        }
        return length;
    }
    

    }


  • 0
    I

    This is not O(n) you have a recursive call of length(...) inside of length() function nested in a loop that preforms in O(n).


Log in to reply
 

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