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

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

a

In this video, we solve the Buy and Sell Stock II.

[amitkulkarni]

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

[srihari]

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

[nayansinghal]

Shall we Bow Down, yeah he is a KING.

[dhairyarajbabbar]

my approach of this question
int maxProfit(vector<int>& a) {
int curr=a[0];
int profit=0;
for(int i=1;i<a.size();i++){
if(a[i]<curr) curr=a[i];
else if(a[i]>curr) {
profit+=a[i]-curr;
curr=a[i];
}
}
return profit;
}

[ShreyaSharma-rkyx]

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

[soumyajitganguly]

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

[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 ❤❤

[akshatgoyal]

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;i<n;i++)
if(values[i]-values[i-1]>0)

return total;
}
}

[ManojKumar-widn]

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

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

[PrashantKumar-ndxf]

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

[sandeeppuvvadi]

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

[dipaligangawane]

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

[muditsingh]

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

[anukulgaurav]

we can do it using only two variable:
int maxProfit(vector<int>& prices) {
int n=prices.size(), buy=prices[0], profit=0;
for(int i=0;i<n-1;i++)
if(prices[i]>prices[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.

[himanshuagrawal]

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.

[pratyushbhatt]

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.

[bokuto]

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

[movieji]

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

[tanujarora]

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