The problem
prices[i] is a stock’s price 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.
Examples
01
- Input
prices = [7, 1, 5, 3, 6, 4]
- Output
5
02
- Input
prices = [7, 6, 4, 3, 1]
- Output
0
Constraints
- 1 ≤ prices.length ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁴
The idea
If you sell on a given day, the best day to have bought is the cheapest day before it. So walk the days once, remembering the lowest price seen so far.
On each day, the profit from selling today is price − lowest; keep the largest. The buy day is the left edge of a window and today its right edge; the window’s left edge jumps whenever a new lowest price appears.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def maxProfit(self, prices: List[int]) -> int: lowest = prices[0] # the cheapest day to buy so far best = 0 for p in prices: lowest = min(lowest, p) best = max(best, p - lowest) # sell today, having bought at the lowest return best