Stock-Trading DP

The problem

You have a week of a stock's daily prices: [7, 1, 5, 3, 6, 4]. You may buy and sell to make money, but you can only hold one share at a time — you must sell before buying again. What is the most profit you can walk away with?

With one buy and one sell, the answer feels easy: buy low, sell high. But the moment the rules add a cooldown after selling, or a fee per transaction, or a hard cap of k trades, the greedy instinct breaks down. These variations form one of the most-asked DP families in interviews, and they all yield to a single idea.

A first attempt

Try every pair of buy day i and sell day j > i, and keep the best difference.

def max_profit(prices):
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            best = max(best, prices[j] - prices[i])
    return best

That is O(n²), and it only handles a single transaction. Once you allow multiple trades with cooldowns or fees, the number of buy/sell combinations explodes and brute force becomes hopeless. You need to track state as you move through the days.

The insight

On any given day you are in exactly one of a small number of states, and each day you move between them:

Track the best profit while holding a share versus not holding one. Each day, update both from the previous day's values. The final answer is the best "not holding" profit — you never want to end still holding.

For the basic unlimited-trades version:

• hold = best profit if you currently own a share.
• cash = best profit if you currently own nothing.

Each day: cash = max(cash, hold + price) (maybe sell) and hold = max(hold, cash − price) (maybe buy). Every variant just adds a state or a term — a cooldown adds a "just sold, must rest" state; a fee subtracts on each sale; a cap adds a transaction-count dimension.

How it works

The code

Unlimited transactions, O(1) space — the template you bend for every variant.

def max_profit(prices):
    if not prices:
        return 0
    hold = -prices[0]   # best profit while holding a share
    cash = 0            # best profit while holding nothing
    for price in prices[1:]:
        cash = max(cash, hold + price)   # maybe sell today
        hold = max(hold, cash - price)   # maybe buy today
    return cash

function maxProfit(prices: number[]): number {
  if (prices.length === 0) return 0;
  let hold = -prices[0];
  let cash = 0;
  for (let i = 1; i < prices.length; i++) {
    const price = prices[i];
    cash = Math.max(cash, hold + price);
    hold = Math.max(hold, cash - price);
  }
  return cash;
}

class Solution {
    int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int hold = -prices[0];
        int cash = 0;
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            cash = Math.max(cash, hold + price);
            hold = Math.max(hold, cash - price);
        }
        return cash;
    }
}

int max_profit(int *prices, int n) {
    if (n == 0) return 0;
    int hold = -prices[0];
    int cash = 0;
    for (int i = 1; i < n; i++) {
        int price = prices[i];
        int sell = hold + price;
        if (sell > cash) cash = sell;
        int buy = cash - price;
        if (buy > hold) hold = buy;
    }
    return cash;
}

int maxProfit(vector<int> &prices) {
    if (prices.empty()) return 0;
    int hold = -prices[0];
    int cash = 0;
    for (int i = 1; i < (int)prices.size(); i++) {
        int price = prices[i];
        cash = max(cash, hold + price);
        hold = max(hold, cash - price);
    }
    return cash;
}

Complexity

The general k-transaction solution keeps hold[t] and cash[t] for each transaction count t, giving O(n × k). When k ≥ n/2 there is effectively no cap, so it collapses to the unlimited O(n) case.

When to use it

Practice

Recap

• Model each day as a small set of states (holding vs not, plus rest or a trade count) and transition between them.
• One forward pass updates all states in O(1) memory; the answer is the best not-holding profit.
• Cooldown adds a state, a fee subtracts on sale, a k-cap adds a count dimension — same skeleton throughout.