I do not understand why buying and selling stock on days gives the maximal profit,
why buying stock on day i and selling the stock on day j where j - i > 1 is not possible to be better than this way? Is there a proof？
It is the same for the total profit if you
- buy(5),sell(7),buy(7),sell(8),making 3 profit
- buy(5),sell(8),also making 3 profit.
You can draw a graph,the most profit is the sum of all these line segments which are increasing.
Thanks! I understand the case when it strictly goes up, but for a more general case,say i = 1 and j = 10 and we do not know the value for 2,3,4....,9, how do we guarantee that buying and selling the stock this way is better than buying it on day i and selling on day j
Say a sequence from i to j, if it is in a non-decreasing order, then the highest profit will be achieved by buying at day i and sell at day j. It's the same as you buy 1 and sell in the next day. If, it is NOT in a non-decreasing order, say at day k, the price goes down. Then you can always sell the share at day k-1, and buy 1 at day k to obtain even more profit.
So to sum up, you will earn the max profit from the sum of each non-decreasing segment. The 2 ways to achieve the max profit are essentially the same, but the second one is easier to implement.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.