DP 41. Longest Increasing Subsequence | Memoization

[@sahilgagan2242]

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 ....

[@parthsalat]

Thank striver, we have God

[@ShivangShandilyaa]

@@parthsalat what???

[@atanunayak6637]

@@parthsalat Bhai tunne alag level ka recursion seekh liya hai😂

[@piyushacharya7696]

@@atanunayak6637 😂😂😂😂

[@ashadahmad6493]

@@atanunayak6637 😂😂😂

[@vikasgupta6701]

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!!

[@MCEParitoshShukla]

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

[@Nikkhil492]

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.

[@factfactorial632]

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

[@stith_pragya]

UNDERSTOOD.........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@vinayakgandhi5690]

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.

[@takeUforward]

Smaller modifications I will leave it on you 😛

[@vinayakgandhi5690]

@@takeUforward Absolutely Sir, thanks for everything 🙂

[@pixelsbyme]

@Vinayak Gandhi can u please share the code of your approach, I am not able to implement it. Thank You!

[@vinayakgandhi5690]

class Solution { public int lengthOfLIS(int[] nums) { int[][] dp = new int[nums.length][nums.length]; for (int i = 0; i < nums.length; i++) { Arrays.fill(dp[i], -1); } int[] max = new int[] { 0 }; sol(0, 0, nums, dp, max); return max[0]; } private int sol(int ind, int prev, int[] nums, int[][] dp, int[] max) { if (ind == nums.length) { return 0; } if (dp[ind][prev] != -1) { return dp[ind][prev]; } int w = -1; int wo = -1; if (ind == prev) { w = 1 + sol(ind + 1, ind, nums, dp, max); wo = sol(ind + 1, ind + 1, nums, dp, max); } else { if (nums[ind] > nums[prev]) { w = 1 + sol(ind + 1, ind, nums, dp, max); } wo = sol(ind + 1, prev, nums, dp, max); } dp[ind][prev] = Math.max(w, wo); max[0] = Math.max(max[0], dp[ind][prev]); return dp[ind][prev]; } }

[@vishalbalaji1842]

Actually, we cannot do this in some cases(ex: gfg lis question), because they mention it has to be strictly increasing

[@ashutoshgupta1905]

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.

[@VedantMahajan-j9e]

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)

[@janardhan2jordan]

that seems like a valid approach Great

[@Ashutoshc777]

@@janardhan2jordan won't work when we have input like 55555 or 22222, output should be 1 but instead it will give length of string

[@ADITYARAJ-yv2tr]

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..

[@jaisamtani303]

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!

[@sauravchandra10]

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.

[@kashyapkumar6255]

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

[@anmoljohri9930]

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& nums) { int n = nums.size(); // vector dp(n+1,vector(n+1,0)); vector 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]; } };

[@pranavchandrode7127]

in take case "take = 1+dp[ind+1][ind+1];" why did you write [ind+1][ind+1] in both, acording to the recursive solution isn't it should be dp[ind+1][ind] ?

[@anmoljohri9930]

@@pranavchandrode7127 yes according to recursion it should be that only , but if you carefully observe you'll notice that indexing changes for tabulation and space optimization, striver has even tried to teach us why that change in indexing happens , i don't remember it as of now , did DP 5 months ago , have to revise again

[@pranavchandrode7127]

@@anmoljohri9930 Thank you! I think this is because of coordinate shifting , we have shift the coordinate of prev_ind by 1 everytime, so instead of writting dp[i][prev_ind] we have to write dp[i][prev_ind +1]

[@anmoljohri9930]

@@pranavchandrode7127 yes this was it as far as I remember

[@Sumeet_100]

Hey bro !! could you plz tell why you have taken ( take = 1+dp[ind+1][ind+1]; ) bcz it must be like (// take = 1+dp[ind+1][ind];) could you plz tell the reason??

[@anuragpandey8165]

its giving tle for map dp ( map mp )

[@tusharyadav5874]

bro map is not right data structure . You should use the unorderd_mpap as the map have insertion,deletion,searching of o(logn) , whereas the unorderd_map have time complexity of o(1) for the operations.

[@prit8360]

People who want top-down approach int fun(int ind,int last,vector &arr){ if(ind==0) return 0; int len=fun(ind-1,last,arr); if(last==-1 || arr[ind]

[@Invincible2203]

that would be ind < 0.

[@madhuryar.p5070]

Love this guy's effort 🤩

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@prabhakaran5542]

Understood ❤ and thanks for explaining runtime error ❤

[@striverdaaadi]

striver strives us forward😍😍

[@Mahi-kr9es]

we can do this sum in other way sort the given elements and apply lcs with given array and sorted array

[@your_name96]

good way, but it increases the time complexity for this though so maybe useful for tougher variations

[@Mahi-kr9es]

@@your_name96 ig it will not increase the tc

[@googlewasmyidea9895]

bruh, in subsequence we have to maintain order of indexes. if youll sort it then how could it be a subsequence

[@310gowthamsagar5]

@@googlewasmyidea9895 the original array maintains the order of indexes, the second array which has only sorted unique elements make sure it is strictly increasing. the LCS of both these arrays should maintain the indexes and at the same time strictly increasing.

[@Ashutoshc777]

won't work when we have input like 55555 or 22222, output should be 1 but instead it will give length of string

[@jai_shree_kanha]

Asked in my Interview at Nation With Namo

[@ayushman_sr]

Apart from DP be aware of there exist more optimised solution. nLogN def lengthOfLIS(self, nums: List[int]) -> int: lis = [] for num in nums: pos = bisect.bisect_left(lis,num) if pos == len(lis): lis.append(num) else: lis[pos] = num return len(lis)

[@varunaggarwal7126]

vector longestIncreasingSubsequence(std::vector& nums) { std::vector dp; // Longest increasing subsequence for (int i = 0; i < nums.size(); i++) { int x = nums[i]; if (dp.empty() || x > dp.back()) { dp.push_back(x); } else { // Perform a binary search to find the correct position to insert x in dp int left = 0; int right = dp.size() - 1; int index = -1; while (left

[@mdadil1810]

bhaiya please do longest arithmetic subsequence of given difference

[@MrGohel-ni2py]

All approachs Memoization,Tabulation,Space optimization in C++ class Solution { public: //simple memoization with prevind shift of 1 // int solve(int ind,vectorarr,int n,int prevind,vector&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& nums) { // int n=nums.size(); // vectordp(n,vector(n+1,-1)); // return solve(0,nums,n,-1,dp); // } //simple tabulation with prevind shift of 1 // int lengthOfLIS(vector& arr) { // int n=arr.size(); // vectordp(n+1,vector(n+1,0)); // for(int ind=n-1;ind>=0;ind--){ // for(int prevind=ind-1;prevind>=-1;prevind--){ // int nottake=dp[ind+1][prevind+1]; // 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& arr) { int n=arr.size(); vectorahead(n+1,0); for(int ind=n-1;ind>=0;ind--){ vectorcurr(n+1,0); for(int prevind=ind-1;prevind>=-1;prevind--){ 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]; } };

[@ntgrn-pr5yx]

understood thank you striver

[@blackhatsamurai9386]

One more approach that can be used is monotonic stack private static int findLongestIncreasingSequence(int[] arr) { Stack st = new Stack(); for(int i = 0; i < arr.length; i++) { while(!st.isEmpty() && st.peek() < arr[i]){ st.pop(); } st.push(arr[i]); } return st.size(); } Let me know your thoughts/corrections

[@dajucoder]

it is throwing compilation errors, please run your code before posting it somewhere, it wastes our time to understand your approach and figure out what the hell you wanted this code to do

[@ritikshandilya7075]

Thankyou for great solution Striver

[@paridhijain7062]

Again, Understood! Loving this series.

[@Deepamkolhe]

I think I have more simpler solution ``` vector lis(n, 1); for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] < nums[i]) { lis[i] = max(lis[i], lis[j] + 1); } } } return lis[n-1] ```

[@utkarshsingh1128]

18:50 good issue

[@the_haryannvi_coder]

Other way if you don't want to shift:- #include int f(int i, int prev, int n, int arr[], vector &dp){ // base case if(i==n) return 0; if(prev!=-1 && dp[i][prev] != -1) return dp[i][prev]; int pick = INT_MIN; if(prev==-1 || arr[i]>arr[prev]){ pick = 1 + f(i+1, i, n, arr, dp); } int notpick = f(i+1, prev, n, arr, dp); if(prev==-1) return max(pick, notpick); else return dp[i][prev] = max(pick, notpick); } int longestIncreasingSubsequence(int arr[], int n){ vector dp(n, vector(n, -1)); return f(0, -1, n, arr, dp); }

[@VenkatGopalakrishnan]

No need to create 2D matrix. just 1D def lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp

[@dhanesh.s]

Can we take prev as element (INT_MIN) instead of index And compare like If( nums[I] > prev) Take = 1 + f(I+1,nums[I]); No take = 0 + f(I+1,prev); Max(take,not); In recursion?

[@dhanesh.s]

Initially take as 0

[@jaisamtani303]

@Dhanesh, see below is the issue u will face according to me if u use prev_value instead of prev_idx @Striver was using f(int idx, int prev_idx) for recursion, when he converted it to memoization array he used dp[idx][prev_idx]. We know that both idx and prev_idx can be till n. So dp array will be of size n*n Your case: Your function becomes f(int idx, int prev_value) for Recursion, when u convert it to memoization array, dp[idx][prev_val]. Now idx can go till n, we cannot guarantee what will be limit for prev_value. If array consists of negative elements then array cannot take negative index, lets say array has 5 very huge elements, then your array will be of 5* huge value instead of 5*5. So using prev_idx is better as we know it will be max array size!

[@googleit2490]

Understood :) Was pretty confused why I am getting runtime error, when I was solving it before completing the chapter. Aug'1, 2023 10:38 pm

[@JayashreeThota]

Thanks Striver for the clear explanation of the approach. Can you please help me understand why is the time complexity n*n? We are traversing through the elements only once considering along with the memoization.

[@vamsikrishnagannamaneni912]

Same doubt :(

[@dhruvilhirpara1795]

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)

[@TakeMydick-ii4mb]

Why?

[@suraj1936]

Love you striver

[@VenkatGopalakrishnan]

def lis(array): def dfs(curr, prev): if curr == n: return 0 if (curr, prev) not in memoize: length = dfs(curr+1, prev) if prev == None or array[curr] > array[prev]: length = max(length, 1+dfs(curr+1, curr)) memoize[(curr, prev)] = length return memoize[(curr, prev)] n = len(array) memoize = {} return dfs(0, None)

[@MaheshKumar-jt3qv]

why we are not using concept that we did earlier, that is starting from back? i am getting lot of confusions

[@piyushacharya7696]

look at this base case then you will understand! 1 2 2 if you start from 0th index then the ans is 2 and if you start from the last index the ans is 1.

[@riyakumari8377]

@@piyushacharya7696 not true thats why we are using pick and not pick we wont pick 2 at last index rather 2 of second last index and then 1 so ans will be 2. You start from start or last doesnt matter anyways.

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@mritunjay3723]

why not take used before ?

[@icongrindsetsfj]

Thank You Legend for showing us all the possible approaches.

[@pixelsbyme]

Memoization Solution without taking n+1 .... ie only making dp[n][n]. // Leetcode : Accepted class Solution { public: int f(int ind, int prev_index, vector &dp, vector &arr, int &n) { if (ind == n) return 0; if (dp[ind][prev_index] != -1) return dp[ind][prev_index]; int len = f(ind + 1, prev_index, dp, arr, n); // not take if (prev_index == n-1 || arr[ind] > arr[prev_index]) len = max(len, 1 + f(ind + 1, ind, dp, arr, n)); // take condition return dp[ind][prev_index] = len; } int lengthOfLIS(vector& arr) { int n = arr.size(); vector dp(n, vector(n , -1)); return f(0, n-1, dp, arr, n); } };

[@rahulsaha332]

your previous is the last index and in the recursion you are increasing the indexes, the logic must be reversed and yeah it is still giving a runtime error :)

[@pixelsbyme]

@@rahulsaha332 It is not giving me error in leetcode. Copy paste the code in leetcode and please check again

[@parthverma7089]

@@rahulsaha332 actually it is giving TLE errror coz of memoization

[@ammanchhetri6716]

didn't even have to watch the video...was able to solve it :)

[@rakeshkumarreddypothireddy8159]

Striver bhai, why you haven't started picking elements from the end of the array?

[@tharunreddy2255]

bro did u got the tabulation solution if we start picking elements from the end

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@ganeshkamath89]

Thanks Striver. Understood.

[@wisdomkhan]

You made it look so easy

[@shivamsharma-oi3gn]

Memoization working code: /* class Solution { public: int Solve(int ind, int prevIndex, vector& nums, vector& memo) { if (ind == nums.size()) return 0; if (memo[ind][prevIndex + 1] != -1) return memo[ind][prevIndex + 1]; int dontTake = Solve(ind + 1, prevIndex, nums, memo); int take = 0; if (prevIndex == -1 || nums[ind] > nums[prevIndex]) take = 1 + Solve(ind + 1, ind, nums, memo); return memo[ind][prevIndex + 1] = max(take, dontTake); } int lengthOfLIS(vector& nums) { int n = nums.size(); vector memo(n, vector(n + 1, -1)); return Solve(0, -1, nums, memo); } }; */

[@sahilranjan324]

1 Comment Bhaiya You Are Great ☺️

[@cockroach_master]

" 10 , come , be my part " :D

[@ayushupadhyaya7656]

Hey Striver A solution of TC(nlogn) and SC O(n) is available at leetcode explore section. Would be great if you can cover that approach as well.

[@siddharthagarwal3927]

bhaiya is lecture ke notes site pe available nahi hai

[@mohitsingh7793]

From index=n to index=0 : Accepted on LC : Memo : int f(int i,int next_idx,int n,vector&nums,vector&dp) { if(i==0) return 0; if(dp[i][next_idx]!=-1) return dp[i][next_idx]; int np=f(i-1,next_idx,n,nums,dp); int p=0; if(next_idx==n+1 || nums[i-1]

[@riyakumari8377]

in memoization why we need to pass i starting values as n and not n-1 and similarly nextIdx as n + 1 instead of n?

[@mohitsingh7793]

@@riyakumari8377 I am assuming index starts with 1 instead of 0 for a string. For index=1,n-1 becomes n: For index=0 ,we pass n-1 I hope it helps.

[@MohanaKrishnaVH]

Awesome Explanation. Understood!

[@kartikrameshchavan6662]

Understood 🙏

[@pranavchandrode7127]

in gfg at test case 111/116 i am getting an error "Abort signal from abort(3) (SIGABRT)" in both memoization and tabulation. can anyone help me with this here's the code int recursion(int i,int prev_ind,int arr[],int n,vector& dp) { if(i == n) { return 0; } if(dp[i][prev_ind+1] != -1) return dp[i][prev_ind+1]; int pick = 0; if(prev_ind == -1 || arr[i] > arr[prev_ind]) { pick = 1 + recursion(i+1,i,arr,n,dp); } int not_pick = 0 + recursion(i+1,prev_ind,arr,n,dp); return dp[i][prev_ind+1] = max(pick,not_pick); } Tabulation code :- vectordp(n+1,vector(n+1,0)); // since in base case we have to assign 0 therefore we can omit it // and can be taken care during the for loops for(int i = n-1;i>=0;i--) { for(int prev_ind = n-1;prev_ind>=-1;prev_ind--) { int pick = 0; if(prev_ind == -1 || a[i] > a[prev_ind]) { pick = 1 + dp[i+1][i+1]; } int not_pick = 0 + dp[i+1][prev_ind+1]; dp[i][prev_ind+1] = max(pick,not_pick); } } return dp[0][0]; }

[@cockroach_master]

10 come be my part , come across and be my part

[@cockroach_master]

dont be my part🙄

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@DevashishJose]

understood thank you so much.

[@cinime]

Understood! Thank you so so so much as always!!!

[@jhonsamuel5813]

Memorization is a technique used in DP

[@naturesrevolution]

here first we run not take till if(ind==n) then we run take?

[@DhruvToshniwal]

Is a 2D dp array necessary? Can't we do it in 1D? Start from the back and and for any i, dp[i] = LIS from inex 0...i ??

[@thallapakuteja2350]

nope beacuse we need the previous index also along with curent index beacuse result changes based on previous element also

[@rahul_rangi]

you can do that , using binary search concept int ceilIdx(int tail[], int l, int r, int key) { while (r > l) { int m = l + (r - l) / 2; if (tail[m] >= key) r = m; else l = m+1; } return r; } int longestIncreasingSubsequence(int nums[], int n) { int tail[n]; int len =1; tail[0] = nums[0]; for (int i = 1; i < n; i++) { if(nums[i] > tail[len - 1]) { tail[len] = nums[i]; len++; } else { int c = ceilIdx(tail, 0, len - 1, nums[i]); tail[c] =nums[i]; } } return len; }

[@abhishuraina4302]

Bhai apki videos next level hai

[@AnkitPandey-s9h]

great content bhai respect for you

[@GungunRamchandani]

UNDERSTOOD

[@arihantjammar8888]

Understood 😊

[@higas7161]

why we always take the first elemnt there might be a case where without it we get a longer inc subsequence ?

[@adityasrivastava3540]

Can someone explain why this wont work? int lmax(vector &nums,int n,int index,int prev){ if(index==n) return 0; int take; if(prev==-1 || nums[index]>nums[prev]){ take=1+lmax(nums,n,index+1,index); } int nottake=0+lmax(nums,n,index+1,prev); return max(take,nottake); } What is the difference?

[@devanshibavaria699]

u need to initialize take with 0. if( the conditions prev==-1 || nums[index]>nums[prev] are not satisfied it will take a garbage value.

[@VikashYadav-px8ei]

Understood 🎉

[@IshmaamIftekhar]

Why (prev-ind) tho instead of prev only? Cause the previous element should be prev if we don't take right??

[@arsh2935]

Bhaiya what to do in case if nums[I] values range from 10^-4 to 10^4 . if I am declaring dp of n x 10^8 , It is showing memory limit exceeded on leetcode

[@takeUforward]

For that bs approach in next video

[@MustafaIrfanAhmed]

for the algorithm(the youtube one), Understood.

[@parambharti7095]

Great content. Thanks a lot striver.

[@TON-108]

Understood!

[@adhirajbhattacharya8574]

Can anyone help? My intuition to solve this with recursion is lisEndingAtI(idx, next) instead of lisStartingAtI(idx, prev). It works out for 2d array memoization. However i am having problem to create the tabulation formula based on this and hence not able to optimize for space through tabulation. Can someone help me to understand the recurrence from lisEndingAtI with next element selement selected?

[@bhagyashri7729]

thanks, test case - [0,1,0,2,3] failing.

[@ParthKanani555]

Hey striver In interview how we decide that the problem is memoized Or not? By drawing recursion tree...

[@harrypottah9862]

18 th Feb

[@sparshbarolia1556]

[@ujjalsaha428]

As always "understood"❤️

[@youtubekumar8590]

Thanku bhaiya

[@impatientgaming9868]

Good one

[@rohandevaki4349]

at 4:23 , can you share on which videos you have taught it ?

[@joya9785]

Guys can someone explain why the time complexity for the memoized soln is O(n^2)?

[@Hello-ro6hr]

UNDERSTOOD ...

[@sameersahu4569]

Understood!!Thank you

[@Aman-lm9jv]

what is wrong in this code someone explain please : int f(int n , vector& nums){ if(n == 0){ if(nums[n] < nums[n+1]) return 1; else return 0; } int notTake = f(n-1 , nums); int take = -1; if(n-1 >= 0){ if(nums[n] > nums[n-1]) 1 + f(n-1 , nums); } return max(take , notTake); }

[@shubhigupta5689]

Understood🌻

[@abdalla4425]

UnderStood. It's Kind of funny that the comments and views get lower as you reach the end of the series. But the comments are always super positive and praising striver!!!

[@aj9706]

Mostly because Many folks don't have Recursion grasp , So they won't be able to understand as the series goes forward.

[@deshdeepakkant524]

bcz they are able to do it without watching tutorial

[@Virtualexist]

I could nt do with a slight variation... What if we are alllowed to swap two of the numbers in the subsequence and then find the longest increasing subseuence? Please suggest.

[@ayushsrivastava458]

I used the following approach( but it is giving wrong answer for some test cases) for finding LIS : First I sorted the given array and then i found the Longest common subsequence between the original array and the sorted array. What is wrong with this approach, it is giving wrong answer for some test cases ?

[@chiragmehta2955]

Bcz it will change order in input Ex. 2 3 1 Lcs=2 If we sort input 1 2 3 Lcs = 3 ehich is wrong

[@10daysAgo]

​@@chiragmehta2955no your explanation is wrong . The LCS after sorting for your example will still be 2 not 3 .

[@tejuchowdary2666]

Understood Bhayya

[@santali-tr3rj]

Striver and striveria teaching co-ordinate on the geo

[@stain5570]

This is my solution class Solution { public: int lengthlo(vector &nums, int po, int prev, vector &dp){ if(ponums[po]) return dp[po][prev] = max(1 + lengthlo(nums, po-1, po, dp), lengthlo(nums, po-1, prev, dp)); return dp[po][prev] = lengthlo(nums, po-1, prev, dp); } int lengthOfLIS(vector& nums) { int n = nums.size(); nums.push_back(INT_MAX); vector dp(n+1, vector(n + 2, -20001)); return lengthlo(nums, n-1, n, dp); } };

[@sejalrai30]

thank you