You are given prices, where prices[i] is the price of a share on day i. You may buy one
share on one day and sell it on a later day.
Return the largest profit you can make. If no trade makes money, return 0 (you simply don't
trade).
Example 1
- Input
- prices = [8, 3, 6, 1, 5, 4]
- Output
- 4
Example 2
- Input
- prices = [9, 7, 4, 2]
- Output
- 0
Constraints
pricesholds 1 to 10⁵ numbers.- Every price is between 0 and 10⁴.
Show the pattern
Sliding window
The best sale on each day pairs it with the cheapest day before it. The sell day slides forward one day at a time, and the buy day jumps forward whenever a new low appears: a window that only ever moves right.
See sliding window in a visualiserShow the approach
Walk through the days once. Keep lowest, the cheapest price so far (the best day to have
bought), and best, the largest profit so far. For each price, first try selling today:
best = max(best, price − lowest). Then update lowest with today's price.
Think of it as a window from the buy day to the sell day. The right end moves every day, and the left end jumps forward whenever a new low appears, since a cheaper start is better for every later sale.
Time: O(n) · Space: O(1)