Best Time to Buy and Sell Stock
Single buy/sell transaction maximizing profit — sweep tracking running minimum.
3 min read
sliding-window array dp
Problem#
prices[i] is the stock price on day i. Buy on one day, sell on a later day — return the max profit (or 0 if no profit possible).
Examples#
[7,1,5,3,6,4]→5(buy at 1, sell at 6)[7,6,4,3,1]→0
Constraints#
1 <= prices.length <= 10^5.
Approach#
Track the running minimum seen so far. For each day, candidate profit = current price − running min; update the best. Equivalent to a sliding window where left only ever moves to a new minimum.
Solution#
class Solution {public: int maxProfit(vector<int>& prices) { int lo = INT_MAX, best = 0; for (int p : prices) { lo = min(lo, p); best = max(best, p - lo); } return best; }};func maxProfit(prices []int) int { lo, best := math.MaxInt32, 0 for _, p := range prices { if p < lo { lo = p } if p-lo > best { best = p - lo } } return best}from typing import List
class Solution: def maxProfit(self, prices: List[int]) -> int: lo = float('inf') best = 0 for p in prices: if p < lo: lo = p if p - lo > best: best = p - lo return bestvar maxProfit = function(prices) { let lo = Infinity, best = 0; for (const p of prices) { if (p < lo) lo = p; if (p - lo > best) best = p - lo; } return best;};class Solution { public int maxProfit(int[] prices) { int lo = Integer.MAX_VALUE, best = 0; for (int p : prices) { if (p < lo) lo = p; if (p - lo > best) best = p - lo; } return best; }}function maxProfit(prices: number[]): number { let lo = Infinity, best = 0; for (const p of prices) { if (p < lo) lo = p; if (p - lo > best) best = p - lo; } return best;}Editorial#
The optimal buy day is, by definition, the cheapest day before some sell day. Sweeping left-to-right and tracking the running min lets us evaluate “if I sell today, what’s the best profit?” in O(1) per step. The recursive DP framing (dp[i] = max(dp[i-1], prices[i] - min[i])) collapses to this exact loop.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#