class Solution { public int lengthOfLIS(int[] nums) { /* 1D array storage- every cell denotes LIS till that cell ,mandatory that LIS ends at that cell moving fromt left to right(small problem to large problem) */ int n = nums.length; //base case if(n == 1)return 1; int dp[] = new int[n]; dp[0] = 1; //LIS for 1 length will be of length 1 int ans = 1 ; for(int i = 1 ; i < n ; i++){ /*finding max LIS in previous elements in dp and also ensuring that current element is greater than last element of previous LIS , as we have already assigned storage ensuring that LIS will end at that element so we already know that last element will be previous element only */ for(int j = i-1 ; j >=0 ; j--){ if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j]); } dp[i] += 1; ans = Math.max(ans , dp[i]); } return ans; /*we are returning ans and not dp[n-1] as dp[n-1] will just store LIS which the and will end at arr[n-1] but we need maximum length so we will store max as we traverse put in values in dp */ } }
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