Best Time to Buy and Sell Stock Series (All 6 Problems)

Core Philosophy: State Machine DP

All stock problems can be unified using a State Machine DP approach:

• State: Day x Transaction Count (k) x Holding State
• dp[i][k][0]: The maximum profit on day i with at most k transactions, not holding stock.
• dp[i][k][1]: The maximum profit on day i with at most k transactions, holding stock.

State Transitions:

dp[i][k][0] = max(dp[i-1][k][0],          // Stayed out
                  dp[i-1][k][1] + prices[i]) // Sold today
dp[i][k][1] = max(dp[i-1][k][1],           // Stayed in
                  dp[i-1][k-1][0] - prices[i]) // Bought today

1. Best Time to Buy and Sell Stock I (k = 1)

Only one transaction allowed.

int maxProfit1(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        maxProfit = Math.max(maxProfit, p - minPrice);
    }
    return maxProfit;
}

2. Best Time to Buy and Sell Stock II (k = ∞)

As many transactions as you like (but you cannot hold more than one share at a time).

int maxProfit2(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        // Collect every price uptick
        if (prices[i] > prices[i - 1])
            profit += prices[i] - prices[i - 1];
    }
    return profit;
}

Greedy Intuition: If tomorrow is more expensive than today, "buy" today and "sell" tomorrow to capture the difference.

3. Best Time to Buy and Sell Stock III (k = 2)

At most two transactions.

int maxProfit3(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);          // First Buy
        sell1 = Math.max(sell1, buy1 + p);    // First Sell
        buy2  = Math.max(buy2,  sell1 - p);   // Second Buy (using profit from first)
        sell2 = Math.max(sell2, buy2 + p);    // Second Sell
    }
    return sell2;
}

4. Best Time to Buy and Sell Stock IV (k = K)

Generalization for K transactions.

int maxProfitK(int k, int[] prices) {
    int n = prices.length;
    // Optimization: If K is large enough, it's equivalent to infinite transactions
    if (k >= n / 2) return maxProfit2(prices); 
    
    int[] buy = new int[k], sell = new int[k];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int p : prices) {
        for (int i = 0; i < k; i++) {
            buy[i]  = Math.max(buy[i],  (i == 0 ? 0 : sell[i-1]) - p);
            sell[i] = Math.max(sell[i], buy[i] + p);
        }
    }
    return sell[k - 1];
}

5. Best Time to Buy and Sell Stock with Cooldown

After selling, you cannot buy stock the next day.

int maxProfitCooldown(int[] prices) {
    int held = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int p : prices) {
        int prevSold = sold;
        sold = held + p;                      // Sell today
        held = Math.max(held, rest - p);      // Buy today or stay held
        rest = Math.max(rest, prevSold);      // Stay resting or enter rest after sold
    }
    return Math.max(sold, rest);
}

6. Best Time to Buy and Sell Stock with Transaction Fee

Every sell operation incurs a fee.

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