DP 41. Longest Increasing Subsequence | Memoization

Please watch the video at 1.25x for a better experience.

a

In this video, we solve the LIS problem with DP. In the next video we have learnt about the next method using tabulation.

[sahilgagan]

73% done …. this is the first time, that i pick a series and consistently practice and learn from it.... u make us doubtless striver.... ur way of explanation is 100x better than any paid courses.... thank god we have striver ....

[vikasgupta]

Able to solve without watching the video. the concepts and basics that you taught so far is now helping me to tackle the problems on my own. Thanks striver!!

[Nikkhil]

The moment you said prev concept trust me striver bhaiya, i somehow was able to understand how to solve this. Thank you man you are a great teacher.

[MCEParitoshShukla]

Bahut Badhiya sir ji sab samajh aa rha h . Bahut sara pyar is series ke liye

[ADITYARAJ-yvtr]

bhaiya you won't believe its been 20 days since i started graph and dp. each day i try to solve alteast 1 question of each topic. i have solved 20 question from each and i haven't reached this question yet but for some placement drive i was just looking for the intuition but as i had already solved the DP on subsequences i was able to build intuition on my within 5 min. in fortunately it is same as yours.

thanks a lot for making this A2Z sheet..

[factfactorial]

Thanks, striver bhaiya !!!
Even the DP array of size n*n would work because the f(n, n-1) will never get stored in dp array because the moment index==n the base case would hit

[ashutoshgupta]

Thanks, striver for the amazing clarity in explanation. Even though the concept and solution is correct, but it would be helpful to stick to bottom up (memoization) and top down (recursion) approach you had from the very beginning.

[sauravchandra]

clearly understood and was able to code it on my own, thanks a lot bhaiya ❤‍🔥!

[OnstreamGaming]

I solved it myself, thanbk you so much for building such a strong foundation.

[vinayakgandhi]

instead of taking -1 as prev when there is no previous index, take prev same as index and check with condition (prev == index), this will not give memory exceed error as you will not need the n+1 2d array, just n will be enough.

[prabhakaran]

Understood ❤ and thanks for explaining runtime error ❤

[jaisamtani]

The good thing is I was able to crack logic for LIS before this video. Did not know that binary search logic is the optimized approach for LIS!


Thanks my intuition for DP problems has become much better than before!

[kashyapkumar]

understood and also thanks for runtime error till know i not sure about "runtime error", today i get one ans from you that is occur due to memory execced

[anmoljohri]

Striver bhaiya you are just our GOD, did till space optimization without watching this video. Cant thank you enough for this brilliant series.

Here's the code:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
// vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
vector<int> ahead(n+1, 0), cur(n+1, 0);

for(int ind = n-1;ind>=0;ind--){
for(int prev = ind-1;prev>=-1;prev--){
// int nottake = dp[ind+1][prev+1];
int nottake = ahead[prev+1];
int take =0;
if(prev==-1 || nums[ind]>nums[prev]){
// take = 1+dp[ind+1][ind+1];
take = 1+ahead[ind+1];
}
// dp[ind][prev+1]=max(nottake, take);
cur[prev+1]=max(nottake, take);
}
ahead=cur;
}
return ahead[0];
}
};

[anuragpandey]

its giving tle for map dp ( map<pair<int, int>, bool> mp )

[VedantMahajan-je]

We can perform a simple lcs on the given vector and its sorted vector(containing unique elements) and solve this😁
create a new vector push the values in the set and then push the values of set in the new vector (set automatically arranges in increasing order) and then run the lcs code(longest common subsequence)

[jai_shree_kanha]

Asked in my Interview at Nation With Namo

[prit]

People who want top-down approach
int fun(int ind, int last, vector<int> &arr){
if(ind==0) return 0;
int len=fun(ind-1, last, arr);
if(last==-1 || arr[ind]<arr[last]){
len=max(1+fun(ind-1, ind, arr), fun(ind-1, last, arr));
}
return len;
}
function starts from fun(n-1, -1, arr)

[dhruvilhirpara]

DP size would be dp[n+1][n+1]; (Just pointing out a small error, Otherwise your content is TOP TIER! BEST CONTENT AVAILABLE OUT THERE)

[MrGohel-nipy]

All approachs Memoization, Tabulation, Space optimization in C++

class Solution {
public:

//simple memoization with prevind shift of 1

// int solve(int ind, vector<int>arr, int n, int prevind, vector<vector<int>>&dp){
// if(ind==n) return 0;
// if(dp[ind][prevind+1]!=-1) return dp[ind][prevind+1];
// int nottake=solve(ind+1, arr, n, prevind, dp);
// int take=INT_MIN;
// if(prevind==-1 or arr[ind]>arr[prevind]){
// take=1+solve(ind+1, arr, n, ind, dp);
// }
// return dp[ind][prevind+1]=max(nottake, take);
// }

// int lengthOfLIS(vector<int>& nums) {
// int n=nums.size();
// vector<vector<int>>dp(n, vector<int>(n+1, -1));
// return solve(0, nums, n, -1, dp);
// }

//simple tabulation with prevind shift of 1

// int lengthOfLIS(vector<int>& arr) {
// int n=arr.size();
// vector<vector<int>>dp(n+1, vector<int>(n+1, 0));
// for(int ind=n-1;ind>=0;ind--){
// for(int
// int
// int take=0;
// if(prevind==-1 or arr[ind]>arr[prevind]){
// take=1+dp[ind+1][ind+1];
// }
// dp[ind][prevind+1]=max(take, nottake);
// }
// }
// return dp[0][0];
// }

//simple space optimization with prevind shift of 1 and ahead and curr arrays

int lengthOfLIS(vector<int>& arr) {
int n=arr.size();
vector<int>ahead(n+1, 0);
for(int ind=n-1;ind>=0;ind--){
vector<int>curr(n+1, 0);
for(int
int nottake=ahead[prevind+1];
int take=0;
if(prevind==-1 or arr[ind]>arr[prevind]){
take=1+ahead[ind+1];
}
curr[prevind+1]=max(take, nottake);
}
ahead=curr;
}
return ahead[0];
}
};