Maximum Profit from Stock Trades
You are given a list prices, where prices[i] is the stock price on day i.
Implement the function:
```python def max_profit(prices): ... ```
Return a two-element list [single, unlimited]:
single— the maximum profit from a single buy-then-sell (buy on one day, sell on a later day). If no profitable trade exists, this is0.unlimited— the maximum total profit with unlimited buy/sell transactions, where you must sell before re-buying. This equals the sum of every upward price move.
Example
max_profit([7, 1, 5, 3, 6, 4]) -> [5, 7]
For a single trade, buy at 1 and sell at 6 for a profit of 5. With unlimited trades, capture every rise: (5-1) + (6-3) = 7.
Hints
- For Part 1: at each day you decide to sell, what is the best day to have bought? You want the minimum price seen before today.
- For Part 1: scan left to right, maintaining the minimum price seen so far. At each step, compute profit if you sell today and update your best result.
- For Part 2: the maximum profit from unlimited trades equals the sum of all positive consecutive differences -- you can always decompose an optimal solution into a series of up-moves.
Worked Solution
Two independent sub-problems on the same price series.
Single transaction — scan left to right tracking the minimum price seen so far. At each day, the best sale is price - min_so_far; keep the largest such value. This is the classic O(n) best-time-to-buy-and-sell.
Unlimited transactions — the maximum total profit equals the sum of all positive consecutive differences prices[i] - prices[i-1]. Capturing every upward step is equivalent to buying at every local minimum and selling at every local maximum.
Both scans are O(n) time, O(1) space, and are computed independently, then returned together as [single, unlimited].
```python def max_profit(prices): # prices[i] is the stock price on day i. # Return [single, unlimited]: # single = max profit with ONE buy-then-sell (0 if no profit possible) # unlimited = max total profit with unlimited buy/sell (sell before re-buying) if not prices: return [0, 0]
# Single transaction: track min price seen so far. min_price = prices[0] single = 0 for p in prices[1:]: if p - min_price > single: single = p - min_price if p < min_price: min_price = p
# Unlimited transactions: sum every positive consecutive gain. unlimited = 0 for i in range(1, len(prices)): diff = prices[i] - prices[i - 1] if diff > 0: unlimited += diff
return [single, unlimited] ```
Intuition
Part 1 is a classic one-pass trick: instead of checking all pairs (buy day, sell day), you notice that for a fixed sell day, the optimal buy day is the minimum of everything before it. Maintain that running minimum and you reduce the problem to a single scan.
Part 2 has a beautiful mathematical structure. Any profit-maximizing sequence of trades on a price series can be rewritten as a sum of consecutive day-over-day gains, because buying at a local minimum and selling at a local maximum is the same as collecting each positive daily increment in between. This decomposition shows that the greedy strategy -- collect every up-move -- is globally optimal. It also illustrates why transaction costs change the problem fundamentally: with a cost per trade, you would need to consolidate small up-moves into fewer larger trades, requiring dynamic programming.