Skip to main content
Stock / State Machine

Buy & Sell Once

Track the minimum price seen so far. At each day, the profit if you sold today = today's price − min price so far. Update the global max profit. One pass, O(1) space. The simplest stock problem.

O(n)
·
O(1)

How It Works

Best Time to Buy and Sell Stock with a single transaction reduces to one linear scan. Maintain the minimum price seen so far; at each day, the profit from selling today is price - minSoFar, and you keep the maximum such profit across the scan while updating the minimum. This works because the best sell day must be paired with the cheapest buy day before it, and the running minimum captures exactly that.

The scan is O(n) time and O(1) space, versus O(n^2) for checking every buy/sell pair. Viewed through the state-machine lens, it is a two-state DP — 'holding' tracks -minPrice and 'sold' tracks the best profit — which is why it serves as the base case for the harder stock variants with cooldowns, fees, and transaction limits.

Step-by-Step Visualization

Best time to buy and sell stock (once)
7
0
1
1
5
2
3
3
6
4
4
5
Min Price7
Max Profit0
1/3

Code

Java
static int maxProfit(int[] prices) {
  int minPrice = Integer.MAX_VALUE, maxProfit = 0;

  for (int price : prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }
  return maxProfit;
}
// maxProfit(new int[]{7,1,5,3,6,4}) → 5 (buy at 1, sell at 6)

Tips & Gotchas

1Track minimum price seen so far
2At each day, profit = current price - min price
3Update max profit if current profit is higher

Practice Problems

  • 1Best Time to Buy and Sell Stock
  • 2Maximum Subarray
  • 3Best Time to Buy and Sell Stock II
  • 4Maximum Difference Between Increasing Elements

About the Stock / State Machine Pattern

Model the problem as states (holding stock, not holding, in cooldown) with transitions between them. Each day, you transition between states based on your action (buy, sell, hold). Track the max profit in each state.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

  • Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • House Robber
  • Longest Increasing Subsequence
  • Word Break

Frequently Asked Questions

How does this connect to Kadane's algorithm?

Transform prices into day-to-day differences; the best single transaction equals the maximum-sum subarray of those differences. Both algorithms carry a running best-ending-here value and reset implicitly when it stops helping, so mastering one gives you the other.

What changes when unlimited transactions are allowed?

With no transaction cap (Stock II), the optimum is simply the sum of every positive daily difference — climb every upslope. A single transaction forces you to pick the one widest valley-to-peak spread instead, which is what the min-so-far scan finds.

Why track the minimum price rather than the maximum?

You must buy before you sell, so scanning left to right the relevant question at each day is 'what was the cheapest earlier buy?' Tracking the max price would answer the reversed question and requires a right-to-left scan to be correct.