The Stock Trading Compendium

State Machine Perspective

All stock trading problems can be unified using a State Machine model with three dimensions: (Day, Transaction Count, Holding Status).

// General Framework for k transactions
dp[i][k][0]: Max profit on day i with k transactions done, NOT holding stock.
dp[i][k][1]: Max profit on day i with k transactions done, CURRENTLY holding stock.

Transitions:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])   // Rest or Sell
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) // Rest or Buy

1. Single Transaction (LeetCode 121)

Find the global minimum price and calculate the maximum potential profit on any subsequent day.

public 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;
}

2. Infinite Transactions (LeetCode 122)

Greedy approach: accumulate all "upward slopes" between adjacent days.

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

3. Two Transactions (LeetCode 123)

Maintain four states representing the maximum profit after each sequential buy/sell operation.

public int maxProfit(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;
    for (int p : prices) {
        buy1  = Math.max(buy1, -p);
        sell1 = Math.max(sell1, buy1 + p);
        buy2  = Math.max(buy2, sell1 - p);
        sell2 = Math.max(sell2, buy2 + p);
    }
    return sell2;
}

4. K Transactions (LeetCode 188)

Generalization of the two-transaction problem. If $k$ exceeds half the number of days, it collapses into the "infinite transactions" case.

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) return maxProfitInfinite(prices);
    
    int[] buy = new int[k + 1], sell = new int[k + 1];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int p : prices) {
        for (int j = 1; j <= k; j++) {
            buy[j] = Math.max(buy[j], sell[j - 1] - p);
            sell[j] = Math.max(sell[j], buy[j] + p);
        }
    }
    return sell[k];
}

5. Stock with Cooldown (LeetCode 309)

Cannot buy on the day immediately following a sale.

public int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int p : prices) {
        int prevSold = sold;
        sold = hold + p; // Sell today
        hold = Math.max(hold, rest - p); // Buy today (must come from rest)
        rest = Math.max(rest, prevSold); // Rest today
    }
    return Math.max(sold, rest);
}

6. Stock with Transaction Fee (LeetCode 714)

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

At a Glance Comparison Table