Q8 Longest Increasing Subsequence - LeetCode 300
Thu Mar 02 2023 08:00:48 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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 */
}
}
content_copyCOPY
https://leetcode.com/problems/longest-increasing-subsequence/
Comments