AC Solution (DFS + DP), Suggestions welcome


  • 0
    C

    Hey Folks,

    I tried a DFS approach with DP and the below solution gets accepted in Leetcode. However, it's pretty slow and i am trying to understand the bottleneck. Please correct me if i am wrong on the time complexity which i think is O(n^2) in this case.

    class Solution {
        public int lengthOfLIS(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int[] dp = new int[nums.length];
            int max = 0;
            for (int i = 0; i<nums.length; i++) {
                max = Math.max(max, solve(nums, i, dp));
            }
            
            return max;
        }
        
        int solve(int[] nums, int start, int[] dp) {
            if (dp[start] != 0) return dp[start];
            int max = 1;
            for (int i = start + 1; i<nums.length; i++) {
                if (nums[i] > nums[start]) {
                    int len = 1 + solve(nums, i, dp);   
                    max = Math.max(max, len);
                }
            }
            
            dp[start] = max;
            return max;
        }
    }
    

Log in to reply
 

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