easyGreedy choice target 15 min
Best day to buy and sell
A list prices holds the price of one share on each day: prices[0] on day 0, prices[1] on day 1, and so on. You may make one trade: buy one share on one day and sell it on a later day. The profit is the sell price minus the buy price.
Return the largest profit you can make. If no trade makes money, do not trade and return 0.
Example 1
Input
prices = [6, 2, 7, 1, 4]Output5Buy on day 1 at 2, sell on day 2 at 7. The cheapest price, 1 on day 3, only leads to 4 - 1 = 3.
Example 2
Input
prices = [9, 7, 4, 3]Output0Prices only fall, so every trade loses money. Do not trade.
Example 3
Input
prices = [5, 8, 2, 9]Output7Buy on day 2 at 2, sell on day 3 at 9. Buying at 5 on day 0 makes at most 9 - 5 = 4.
Constraints
1 ≤ len(prices) ≤ 105
0 ≤ prices[i] ≤ 104
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.