DP 36. Buy and Sell Stock - II | Recursion to Space Optimisation

[@amitkulkarni9682]

In my entire life, I'll always remember this special guy. Always.

[@Mohit_Q]

bro you are from which batch ?

[@srihari5605]

Guys, along with this dp approach, greedy also works in this problem. If you are curious: If the stock price of tomorrow is greater than today, buy it today and sell it tomorrow. (it is as greedy as it can be.) sum of all the profit is automatically the maximum profit anyone can get. sum = 0 for i in range(1, len(prices)): sum += (prices[i] - prices[i-1]) if prices[i] >= prices[i-1] else 0 return sum

[@Dontpushyour_luck]

thank you for explaining how greedy works here. greedy is indeed tougher than dp as it is tougher to get through observation that greedy will work.

[@priyansh8656]

@@Dontpushyour_luck for recognizing the greedy can be used or not what I try to do is plot on a paper the numbers in the array or similar things and then if on sudden increase or decrease something happen then it gives a possibility of greedy> So far this approach has worked for me as here also while increasing do nothing the moment it decreases you need to sell it

[@DipsNohawar]

@@priyansh8656 can you elaborate this intuition more ?

[@siddharthchauhan961]

Don't understand how greedy will be correct here.. If let's say there's an array [5,3,8], then buying stock on the first index(price=5) itself is a worse decision than buying stock on 2nd index(price=3) since in both cases the selling price will be 8 but the buying price is different?

[@piyush2776]

@@siddharthchauhan961 Greedy is applied on consecutive days. So only when successive day is larger than previous day we mark it as profit. In you example we will compare 5,3 since 3 is smaller we'll skip this iteration then we'll compare 3,8 since 8 is larger we'll count different as profit. Hope this helps.

[@ShreyaSharma-rk4yx]

i dont know how long my journey will go but for sure you are the best teacher ever❤❤

[@Beeplov2337568]

The Best 💫

[@girishthatte]

Thankyou so much Striver for your awesome DP Playlist. I was able to solve all the 6 variants of DP on stocks starting from recursion to space optimization very easily in one shot and in less time as well. This playlist is top-notch and I have got good confidence now in DP. Keep up the good work. No one can teach at your level. You are the best ❤❤

[@nayansinghal23]

Shall we Bow Down, yeah he is a KING.

[@OnstreamGaming]

Man, Man , Man, This is the striver for you , with GOD explanation .I was like no matter how long the video will be its going so smooth ill watch till end.

[@ManojKumar-wi2dn]

I WAS DOING THESE QUES FOR 2 WEEKS AND BY JUST SEEING THIS SINGLE VIDEO, I CAN DO ALL QUES ON STOCKS...THANKS A LOT

[@dhairyarajbabbar7584]

my approach of this question int maxProfit(vector& a) { int curr=a[0]; int profit=0; for(int i=1;i

[@WYNTL6980]

Great approach !!! TC = O(n) and SC= O(1). I request Mr Striver to highlight this comment for everyone to see.

[@OnstreamGaming]

@@WYNTL6980 ya its greedy approach

[@Dontpushyour_luck]

Without watching your video, I solved this question on my own. Finally I am beginning to see through dp. I know I am yet a beginner in dp, but I shall learn dp so good that I would be able to do dp hard questions on codeforces. I know that it will be a long journey, but thank you for building my foundation so good. Dp is not intuitive at all but atleast for a beginning I am able to look into the intuition of dp.

[@joshuamanivinod9873]

How is your progress? :)

[@Dontpushyour_luck]

@@joshuamanivinod9873 pretty good. I have completed this playlist and now I am able to do dp without any fear. I am also able to understand solutions that others give for dp questions, whereas before I couldn't understand a bit of it.

[@055muditsingh7]

I am stuck with this problem for a few days, but after watching your video, I am able to solve the problem. Thanks Bhaiya .

[@soumyajitganguly2593]

Good effort to link the (more general) recursive approach to DP to 4 variable approach. But this problem can be solved from intuition in a very simple way using just 1 extra variable. Just compare today with yesterday and sell to make immediate profit (if today > yesterday). Keep doing so: profit += today - yesterday

[@vimalslab3398]

yes ... I solved this Q previously in this way. At that time I had no idea of dp.

[@tusharnain6652]

@@vimalslab3398 same bro!

[@adityaajay29]

yeah, greedy works great here

[@amandixit3555]

this is not intution , intution should have proof.

[@Gurrari]

@@amandixit3555 Good point, at first, i also solved it without using recursion, but now i see, that isn't very logical and intuitive, its just a flick that greedy worked here.

[@PraSHanTlifts78]

this guy is a machine i'm not gonna forgot that he used unsleeply nights to reacord the videos for ourself

[@parthh3963]

us*

[@kshitiz1107]

@@parthh3963 xd

[@stith_pragya]

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

[@bokuto3641]

You don't know how much we all waited for this ❤️...Keep up the good work bhaiya...Good luck and have all our blessings 🥳

[@akshatgoyal9113]

Recurrence isnt required for this question either. You can simply buy the stock on every day and sell it either on the same day if the next day has a lesser value or sell it next day and buy it again if it has a greater value. Time Complexity-> O(N) Space Complexity->O(1) public class Solution { public static long getMaximumProfit (int n, long[] values) { if(n==0) return 0; long total=0; for(int i=1;i0) total+=values[i]-values[i-1]; return total; } }

[@dipaligangawane980]

The way you explain is wonderful. Thank you so much Striver. I get addicted to this series.

[@AshishKumar-ww1mr]

same bro . its like some kinda webseries that provides good dopomine

[@immortal6978]

Understoood , but afer watching it twice . finally Hell lot ot effort requires to make and consume the video fruitfully. 😎😎😎😎😎😎

[@prathameshlohar3585]

Thanks Striver, I just watched this video and did other variations on my own.

[@himanshuagrawal8012]

I am glad you explained the four variable solution, it was nightmare to understand that solution from discuss section. I solve by myself till 2 array optimization. UNDERSTOODDDDDDDD

[@bhargav1811]

How on earth can anyone get this type of intution to solve this type of problem?? Each problem with its own unique style !! DP just blows my mind !! Hope that I might can solve this type of problem one day by my own !!

[@movieji5535]

Watch this and next4 can be done easily with few minor changes very grateful to you for this striver

[@tanujarora4906]

I got this in an Interview for a small Startup, could not solve it. As My whole DP Chapter was Pending. Thanks Striver ❤

[@itsaryanb9316]

Damn Striver, your lectures are helping me alot in solving such problems without the need of watching the entire video !! Watched this video till recursion part, and did solved this Question from memoization to space optimisation on my own😀😇 Thanks Alott

[@RohitKumar-dy2gc]

what an amazing approach the final one😊

[@tanyaahuja7424]

You are commendable, the efforts you put in making these videos, helps us to understand clearly. You teach the concept, through which we can solve any problem!! Keep up the hard work, and thank you !! 🙏🙏🌸🌸

[@ajaybabupatel1665]

Striver you lied that it's one of best DP series available! Its not one of Best its THE BEST. Thanks a lot MAN.

[@pratyushbhatt1712]

For anyone who is wondering why recursion started from 0->end here and not from end->0. Here is why The backward approach fails because it violates the logical sequence of buy-sell decisions: In a backward approach, you might decide to "sell" at a later date before you've "bought" at an earlier date. This leads to situations where you're trying to maximize profit from transactions that aren't valid (selling before buying). Let's trace both approaches for prices [1, 2, 3]: Forward recursion: At day 0 (price 1): Buy At day 1 (price 2): Sell At day 2 (price 3): Buy Profit: -1 + 2 - 3 = -2 (Buy at 1, sell at 2, buy at 3) Backward recursion: At day 2 (price 3): Sell (But we haven't bought anything yet!) At day 1 (price 2): Buy (This doesn't make sense given our "sell" at day 2) At day 0 (price 1): Sell (Again, we can't sell what we haven't bought) The backward approach leads to illogical decisions because it's considering selling before buying.

[@priyajaiwal8072]

Great insight, what i dont get is why is dp table filled from backwards?

[@sahilrepuriya3205]

This is mind blowing🤯 .Understood sir thanks alot💙

[@gaurabdas1510]

Understood! Also greedy solution is the best for this problem (C++ solution) - TC - O(n) and SC - O(1) long getMaximumProfit(long* values, int n) { if(n

[@sahilbadkul7130]

Good morning sir, Understood this problem very well. Best explanation ever. I solved this problem lot of times by seeing solution in discussion forms but never understood, But today I understood this very well, never forgot this again. Thank you so much.

[@rohitchanda8461]

What an explanation! Never imagined that this question could be converted to such easy algebraic technique!

[@DeadCode_Debugs]

he is the GOAT of dsa

[@tahaansari5621]

Here's the greedy approach in Java: Intuition: The logic essentially captures all upward price trends and adds the profit from each trend to the cumulative profit int cumProfit = 0; for(int i = 1; i < prices.length; i++) if(prices[i] > prices[i - 1]) cumProfit += prices[i] - prices[i - 1]; return cumProfit;

[@kashifzaidi152]

Explaination is really amazing!!!

[@tusharnain6652]

You can also use greedy, it's more optimal in this problem, below is c++ code int maxProfit(vector& prices) { int profit = 0; for(int i = 0; i < prices.size()-1; i++) if(prices[i] < prices[i+1]) profit += prices[i+1] - prices[i]; return profit; }

[@rishabhkumar8115]

but how it works. Give some proofs as well

[@tusharnain6652]

@@rishabhkumar8115 whenever you see that arr[i+1] is more than arr[i], consider trading, that's it.

[@rishabhkumar8115]

@@tusharnain6652 but there is no uniformicity of data. there is possibility of getting more profite by selling current stock on other day after (i+1)th day.

[@tusharnain6652]

@@rishabhkumar8115 yes, you're right. Damn, they should add more testcases.

[@jatinmalhotra2325]

​@@rishabhkumar8115 True there is a possibility of getting more profit by selling current stock on other say after (i+1)th day but that will still result in same net profit. consider a case like [p1 p2 p3] where p1< p2

[@crazyduniya128]

26:33 Same thing I did in the last two lines. No Words❤‍🔥

[@adityapatel_00]

I don't know why this code works but... I think it is the most optimal code so far. long profit=0; for(int i=0;i

[@nihalsingh6233]

This is the greedy approch. Institution is very simple : If the stock's price is increased tomorrow as compare to today, we will buy it and in last we will return our total sum

[@priyajaiwal8072]

Why are we starting dp from backwards? 1. Future Decisions: When you're at a given day (index), you need to know the results of future days to make optimal decisions. By iterating backwards, you can compute the maximum profit for each day based on the future days' profits. 2. State Transition: The state transitions depend on future states: If you're in a "buy" state, you consider: >Buying today and then looking at the profit from tomorrow. >Not buying today and looking at tomorrow's profit. If you're in a "sell" state, you consider: >Selling today and then looking at tomorrow's profit after buying. >Not selling today and looking at tomorrow's profit.

[@snehalshaevya5598]

Striver, you don't even need the currBuy and currNotBuy variables. A great explanation, thanks for this DP series its really amazing.

[@anukulgaurav3043]

we can do it using only two variable: int maxProfit(vector& prices) { int n=prices.size(),buy=prices[0],profit=0; for(int i=0;iprices[i+1]){ profit+=(prices[i]-buy); buy=prices[i+1]; } profit+=(prices[n-1]-buy); return profit; } Logic - assume we sell whenever price drops and buy next day.

[@vimalslab3398]

class Solution { public: //kzbin.info/www/bejne/aYStZKOLoLWEg8U int maxProfit(vector& p) { int n = p.size(); int ans = 0; for(int i = 1;i p[i-1]){ ans += (p[i] - p[i-1]); } } return ans; } };

[@dxvya23]

Brilliant teaching skills ..hats off

[@ratanprakash8075]

I solved it using JUST 2 VARIABLES. Most space optimised simple solution.

[@PujaSingh-qg5ln]

Awesome explanation. Great work!!

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@magantisrikanth143]

best explanation ever

[@vaibhavdangayachvd]

13:52 When we can buy and we decide to buy , why are we incrementing the `ind` for the next recursive call ?

[@chiragkhemani1615]

Because we have to jump to next day or elemnt of an array

[@varunsharma1889]

If u don't then you will end up making the recursive call for the same index forever ♾️

[@ankitkumar-fy2om]

I don't think there is need for DP here, this can be solved greedily. My approach: int maxProfit(vector& prices) { int total_profit = 0; int buy_price = prices[0]; for (int i = 1; i < prices.size(); ++i) { if(prices[i] < prices[i - 1]) { total_profit += (prices[i - 1] - buy_price); buy_price = prices[i]; } } total_profit += (prices[prices.size() - 1] - buy_price); return total_profit; }

[@Porsche911Dream]

Excellent explanation!!! Btw this can be solved without dp as well in O(n). Intuituion is similar, if we don't have stock we can only buy. If we have it we will update buy price if current value is lower than our buy price else we can sell it. While selling we'll keep going as long as we're getting higher value. long getMaximumProfit(long *values, int n) { bool hasStock=false; long buy=0,profit=0; for(int i=0;i

[@pulkitjain5159]

ya , i thought for the greedy approach to just buy on the local minimas and sell it on local maximas

[@ritikrawat2447]

Memorization in java , giving stackOverflow Error

[@tasneemayham974]

Best TEacher Everr!!!

[@prateeksharma3698]

Solution's journey is very exciting , and yes I understood the problem.

[@ritikshandilya7075]

Thanks for amazing solution striver

[@preetisahani5054]

Understood, Indeed it was amazing

[@rohitanand7071]

Understood Also there is no need to carry cur array

[@prashantrai5102]

Its 5:41 a.m in the morning 🤩🤩🤩 .... OHH My god .... dedication level ultra pro maax

[@ethanhunt8001]

You have no idea how eagerly I was waiting for videos

[@meghanshmundra1070]

NOTES ARE NOT THERE FOR THIS LECTURE??????? NOTES ARE NOT UPLOADED AFTER LECTURE 34

[@rohannaik4688]

public int maxProfit(int[] prices) { int sum = 0; for(int i=1;i prices[i-1]) { sum += prices[i] - prices[i-1]; } } return sum; } Time Complexity : O(n) Space Complexity : O(1)

[@shubham007121]

dont be greedy, its dp

[@satendra6200]

Here you can sell the stock and then you can buy the same stock on the same day(if it is less than the next stock price) i.e same index value act as the selling as well as buying.....correct me if i'm wrong

[@nikhilsrivastava7719]

Understood Amazing! But this works too int maxProfit(vector& prices) { int profit = 0; int n = prices.size(); for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; } return profit; }

[@karthikmenon1608]

so when we sell cant we buy on the same day again which eq takes care of that because after selling we are going to next index directly so we wont be able to buy on same day.

[@pulkitagrawal1456]

It can be solved like the previous question easily too class Solution { public: int maxProfit(vector& prices) { int ans = 0; int mini = prices[0]; int n = prices.size(); int profit; int prev = mini; for(int i = 1; i < n; i++) { profit = prices[i] - mini; if(profit > 0) ans = ans + profit; mini = prices[i]; } return ans; } };

[@balveerguleriya8668]

greedy is also working, that too with extremly simple and efficient code.

[@mayanksamadhiya8908]

We can also do this with just using single 2 size array that we have learnt....... Thanks Striver

[@vaibhavbhosale2530]

Understood 👍

[@debjitchakraborty7676]

I think the base case should look like this for tabulation dp[values.length-1][0] = values[prices.length-1]; dp[values.length-1][1] = 0; Because when we are at n-1 position, and if we have no option to buy then definitely we will sell.

[@sanasainath7758]

excellent logical way

[@santoshb7776]

Understood sir !!🙏🙏

[@santoshpokhrel7693]

can't we write recursive solution staring form the last index of the price array instead of first?

[@dhanashreegodase4445]

why we returned dp[0][1] in tabulation? by not dp[0][0]

[@studynewthings1727]

Because 1 indicates you can purchase stock, you don't have any stock to sell, whereas 0 represents to sell the holded stock. Meaning with dp[0][0] meaning you are carrying the profit(i.e. answer) with some stocks yet to sell. Therefore returning dp[0][1]

[@anuragsekhri2315]

explained so well

[@googleit2490]

Done and dusted in the DP revision :) (1 min) Nov'17, 2023 10:21 pm

[@Nutrino259]

2027' graduation guy reacting to a human machine!!!!🤖🤖🤖

[@SOUVIK-po9jt]

@@Nutrino259 Which college

[@mohitsingh13]

Understood ❤

[@shankhadeepbanerjee252]

amazing explanation!

[@DevashishJose]

Understood Thank you so much

[@ranadipmunda9095]

Why we r returning dp[0][1] instead of dp[0][0] in tabulation?

[@someshjoyguru]

Because you already sold the stock you were holding. And now you are about to buy (you are in buy state) (actually you are ending the trading empty handed)

[@ayushgupta80]

if(n ==0) return 0; long buy = values[0]; long res = 0; for(int i =1;i values[i]) { res += values[i-1] - buy; buy = values[i]; } } return max(res,res + values[n-1]-buy); most optimised

[@Himani-t3g]

understood!

[@SunnyGuptaTech]

The way you have explained this is pretty awesome. Keep up the good work Raj bhai. Thank you once again.

[@abhinavmonga9910]

in dp ,at the last step why we are not returning max(dp[0][0],dp[0][1]);returning only dp[0][1] means we are always buying the stock at index 0???

[@cypher7536]

OMG!!!!!!! excellent optimisation...👌👌

[@hoperadas6010]

why we have used dp[n][2] in memoization whereas dp[n+1][2] in Tabulation ??? plz help finding hard to understand it

[@takeUforward]

In memoization you dont store the N the index as you return from base case. In tabulation you Store it, so you need n+1 size to have nth index

[@hoperadas6010]

@@takeUforward Thanks a lot @take U forward !! Very glad to see that you are still putting extra time to solve doubts here in comments. Means a lot!!

[@stephenh7788]

@takeUforward please explain the below code:- class Solution { public: int maxProfit(vector& prices) { int n=prices.size(); vector dp(2,0); for(int ind=n-1;ind>=0;ind--){ dp[0]=max(dp[1]+prices[ind],dp[0]); dp[1]=max(dp[0]-prices[ind],dp[1]); } return dp[1]; } };

[@rajeshseptember09]

Needless to say, great work. But in the DP tabulation approach, why are we returning dp[0][1] at the end ? Shouldn't we return Max(dp[0][1],dp[0][0]) ? Can someone clarify on this please ?

[@No-w4y]

ig there’s no point of using dp[0][0] as you cannot sell it (as dp[i][0] denotes bought and dp[i][1] not bought)

[@joshrak3412]

I think two array space optimisation is more readable and easier than 4 variable space optimisation..

[@VarunPattikonda]

Why tabulation iterating from 0 to n-1 doesnt work for this problem?

[@deep1998-j1v]

Can anyone pls answer my query? If we write the base case in recursion as 0 to n-1, does it mean that in tabulation, it will be reversed (n-1 to 0) always?

[@niteshkushwaha9493]

It's all about understanding this question and all of it's variations can be easily solved.

[@manishchandrapaneru.o5]

G.O.A.T.🔥

[@mdzeeshan1636]

Time and space complexity for both solutions, first using two 2 sized array and second using 4 variables will be same, right??

[@r.s.k1301]

int maxProfit = 0; for(int i=1;iprices[i-1]){ maxProfit+=prices[i]-prices[i-1]; } } return maxProfit; this is better right?

[@sangeethm1984]

profit=0 for i in range (1,len(prices)): if prices[i]>prices[i-1]: profit+=prices[i]-prices[i-1] return profit

[@arjunrai4937]

here is the tabulation solution is top down and the recursion + memoization solution is bottom up right?

[@parthgoswami7493]

Why can't we sell on the last index? I did not get that base case

[@devanshrai8972]

This can be solved without dp class Solution { public: #define loop(i, l, n) for (int i = l; i = n; i--) int maxProfit(vector& prices) { int ans = 0; int n = prices.size(); loop(i,1,n-1) { if(prices[i]>prices[i-1]) { ans+=prices[i]-prices[i-1]; } } return ans; } };

[@juniorboy1903]

Understood bhaiya love this series😍😃

[@garrykevin97]

Is there any explanation on why in tabulation we start from n

[@sandeeppuvvadi4433]

A much simpler approach long profit = 0; for(int i=0;i values[i]){ profit = profit + (values[i+1]-values[i]); } } return profit;

[@muthupandideivamsanmugam1774]

int maxProfit (vector& prices) { int profit = 0; int buy = prices[0]; int n = prices.size(); for (int i = 1; i prices[i]) buy = prices[i]; profit += abs(buy -prices[i]); buy = prices[i]; } return profit; } My O(n) solution anyway thanks for dp solution bhai 😍