Best day to buy and sell
EasyStuck?
Show a hintHide the hint
Walk forward remembering the lowest price seen so far. At each day, the best sale today is today's price minus that low.
The ideas behind this problem
Next in this lesson
Squeeze out the duplicatesYou are given the price of something on each day. Buy on one day and sell on a later day. Return the largest profit possible, or 0 if every choice loses money.
Worked example#
For prices [7, 1, 5, 3, 6, 4], walk forward keeping track of the cheapest price seen so far:
| day | price | cheapest so far | profit if sold today | best profit |
|---|---|---|---|---|
| 0 | 7 | 7 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 2 | 5 | 1 | 4 | 4 |
| 3 | 3 | 1 | 2 | 4 |
| 4 | 6 | 1 | 5 | 5 |
| 5 | 4 | 1 | 3 | 5 |
So the answer is 5: buy on day 1 at 1, sell on day 4 at 6.
The insight is that you never need to look backwards. On any given day, the best you could do by selling today is today's price minus the cheapest price you have seen, and you already know that cheapest price from walking forward.
Constraints#
1 <= n <= 1000000 <= prices[i] <= 10000
Input
prices is a count then that many integers.
Output
The largest profit, or 0.
Examples
Input
6 7 1 5 3 6 4
Output
5
Buy at 1 on day 1, sell at 6 on day 4.
Input
5 7 6 4 3 1
Output
0
Prices only fall, so the best move is not to trade.
Input
2 2 4
Output
2
Buy at 2, sell at 4.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.