class Solution { public int lengthOfLIS(int[] nums) { /* LIS in O(nlogn) -> shorturl.at/tyJZ7 we make a dp array of length n where every cell denote the last element of ith length LIS , we make an upperbound function which returns the just greater or equal to target index where we keep updating the values if we encounter another smaller value than previously stored at index we do this so that we can make a longer LIS in the future , in the end we traverse reversely and at any index if we find value other than INTMAX we return that index + 1 which denotes length of MAX LIS; */ int n = nums.length; int[] dp = new int[n]; Arrays.fill(dp , Integer.MAX_VALUE); //traverse the array use upperbound function to update values for(int i = 0 ; i < n ; i++){ int idx = upperBound(dp , 0 , i ,nums[i]); dp[idx] = nums[i]; } //traverse reversely to find the max LIS for(int i = n-1 ; i>=0 ; i--){ if(dp[i] != Integer.MAX_VALUE) return i+1; } return -1; //will never reach this statement } //upperbound returns just greater or equal to value index for updating value public int upperBound(int[] dp , int low , int high , int target){ while(low <= high){ int mid = low + (high - low)/2; if(dp[mid] == target) return mid; else if(dp[mid] > target) high = mid-1; else low = mid+1; } return low; } //using n+1 as we cant store -1 as index therefore we shift it by 1 //Recursion->exponential Memo-> n*n+1 public int solve(int[] nums , int i , int prev , Integer[][] dp){ if(i == nums.length ) return 0; if(dp[i][prev+1] != null) return dp[i][prev+1]; int len = 0 + solve(nums , i+1 , prev,dp); if(prev == -1 || nums[i] > nums[prev]) len = Math.max(len , 1+ solve(nums , i+1 , i,dp)); return dp[i][prev+1] = len; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter