You are given prices, where prices[i] is the price of a stock on day i. You may buy on one day and sell on a later day, at most once. Return the largest profit you can make, or 0 if no trade makes money.
Example 1
Input: prices = [7,1,5,3,6,4]
Output: 5
Buy on day 1 at price 1 and sell on day 4 at price 6, profit
6 - 1 = 5.Example 2
Input: prices = [7,6,4,3,1]
Output: 0
Prices only fall, so the best choice is not to trade.
Constraints
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4
Hints
Frequently asked at: Amazon, Microsoft, Google, Goldman Sachs, Flipkart, Accenture
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force checks every pair (buy, sell) with buy before sell, which is O(n^2). But if you decide to sell on day i, the best buy day is simply the cheapest day before it. So a single pass that tracks the running minimum price gives the best profit for every sell day, and we keep the maximum.
Algorithm
- Set
minPriceto a very large value andbestto 0. - For each price, update
minPrice = min(minPrice, price). - Update
best = max(best, price - minPrice). - Return
bestafter the loop.
Time:
O(n)Space: O(1)Interview tip: A common follow-up is "unlimited transactions" (Stock II): there you simply add every positive day-to-day difference. Be ready to explain why that greedy works.
class Solution: def maxProfit(self, prices: List[int]) -> int: min_price = float('inf') # cheapest buy so far best = 0 for p in prices: min_price = min(min_price, p) best = max(best, p - min_price) # sell today return bestCtrl + Enter runs the examples