Is this O(n^2)? It shows LTE


  • 0
    J
    public class Solution {
    int LIS=0;
    public int lengthOfLIS(int[] nums) {
        int max = 0;
        if (nums == null || nums.length<1) {
            return 0;
        }
        if (nums.length==1)
           return 1;
        for (int i=0;i<nums.length;i++)
            dfs(nums,i,1);
        return LIS;
    }
    public void dfs (int[] nums, int index, int counter){
        LIS = LIS < counter ? counter : LIS;
        for (int j = index+1; j < nums.length;j++) {
            if (nums[j]>nums[index]) {
                counter++;
                dfs(nums,j,counter);
                counter--;
            }
        }
            
    }
    

    }


  • 0
    Q

    You have for loop in the lengthOfLIS that calls dfs method. dfs method has another for loop, and it recurively calls itself from the for loop... Potentially much much worse than O(n^2)


Log in to reply
 

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