Discussion on "Best time to Buy and Sell Stocks - A comprehensive Guide"

Mrinalini Bansal · 2021-05-03T18:19:26.395Z

Best time to buy and sell stocks is one of the most popular type of problem series asked in various interviews. The problem basically consists of the prices of stocks on each day and requires us to find the maximum profit that can be obtained by buy...

Hi, regarding to problem IV, you mentioned

approach 2
For every stock, calculate cash in hand after buying and selling it in the two arrays. This is done in a loop j from 1 till k where j denotes the cash in hand after jth buy and sell.

so j is from 1 to k

but in code, j is from k to 1?

btw, your linkedln is locked and can't send message

Yes j is from k to 1, by mistake I wrote 1-k. Thanks for pointing it!

j runs from k to 1 because for a current price i, if I decide to buy it at kth transaction, I would subtract this price from my profit at j-1.

j can't run from 1 till k because then profit at j-1 would contain the value of profit after selling current price itself at k-1 th transaction. Hence we move from back so that our value at jth transaction doesn't get affected by values of current price from different situations where we can buy and sell it.

Mrinalini Bansal Thank you for explanation, this is a beautiful solution.

I've been studied for this solution for 2 days and finally get the idea.

However, I still don't know how to get to this solution from observing optimal substructure. I don't know what is the optimal substructure and also how to get to the recursive function from optimal substructure?

Search Hashnode

Best time to Buy and Sell Stocks - A comprehensive Guide

Responses1