Stock Trading

The Best Time to Buy and Sell Stock family models daily prices and asks for maximum profit under different transaction rules. All variants share a state-machine DP pattern: at each day you are either holding or in cash, and you transition by buying, selling, or resting. This lesson covers Stock I–IV (LeetCode 121, 122, 123, 188), cooldown and fee variants, and solutions in C, Java, and Python with trace tables.

Overview & State Machine

Given an array prices[i] = price on day i, you may buy and sell shares (one share at a time in the classic formulation). Profit = sell price − buy price. Rules differ by how many complete buy→sell cycles you may perform.

State machine (general idea):

  cash ──buy──► hold
   ▲              │
   └──sell────────┘

At day i, update:
  hold = max(hold, cash - prices[i])   // buy today (or keep holding)
  cash = max(cash, hold + prices[i])  // sell today (or stay in cash)

Stock I:   at most 1 complete transaction  → track min price seen
Stock II:  unlimited transactions           → greedy sum of ups, or 2-state DP
Stock III: at most 2 transactions           → buy1, sell1, buy2, sell2
Stock IV:  at most k transactions           → dp[t][i] or rolling max_diff

Stock I — One Transaction

Problem (LeetCode 121): Pick one buy day and one later sell day to maximize profit. If no profit is possible, return 0.

Insight: Scan left to right. Track the minimum price seen so far. At each day, candidate profit = prices[i] − min_price. Keep the maximum.

Complexity: O(n) time, O(1) space.

Stock I Code (C, Java, Python)

Python

def max_profit_one(prices):
    """LeetCode 121 — one transaction. O(n) time, O(1) space."""
    min_price = float('inf')
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best


if __name__ == "__main__":
    tests = [[7, 1, 5, 3, 6, 4], [7, 6, 4, 3, 1], [1, 2]]
    for prices in tests:
        print(f"maxProfit({prices}) → {max_profit_one(prices)}")

Java

public class StockOne {

    /** One transaction — track minimum price seen so far. */
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int best = 0;
        for (int p : prices) {
            minPrice = Math.min(minPrice, p);
            best = Math.max(best, p - minPrice);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4})); // 5
        System.out.println(maxProfit(new int[]{7, 6, 4, 3, 1}));     // 0
        System.out.println(maxProfit(new int[]{1, 2}));                // 1
    }
}

C

#include <stdio.h>
#include <limits.h>

int min2(int a, int b) { return a < b ? a : b; }
int max2(int a, int b) { return a > b ? a : b; }

int max_profit_one(int prices[], int n) {
    int min_price = INT_MAX, best = 0, i;
    for (i = 0; i < n; i++) {
        min_price = min2(min_price, prices[i]);
        best = max2(best, prices[i] - min_price);
    }
    return best;
}

int main(void) {
    int a[] = {7, 1, 5, 3, 6, 4};
    int b[] = {7, 6, 4, 3, 1};
    printf("%d\n", max_profit_one(a, 6)); /* 5 */
    printf("%d\n", max_profit_one(b, 5)); /* 0 */
    return 0;
}

Stock I Output & Trace

Program output

Trace for [7, 1, 5, 3, 6, 4]

Stock II — Unlimited Transactions

Problem (LeetCode 122): You may complete as many transactions as you like (but only one share at a time — must sell before buying again).

Greedy insight: Capture every upward day-to-day move. If prices[i] > prices[i−1], add the difference to profit.

DP equivalent: Two states cash and hold updated each day — same O(n) result.

Stock II Code (C, Java, Python)

Python

def max_profit_unlimited_greedy(prices):
    """LeetCode 122 — greedy: sum every upward move. O(n) time."""
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit


def max_profit_unlimited_dp(prices):
    """Same answer — 2-state DP (cash / hold)."""
    cash, hold = 0, -prices[0]
    for p in prices[1:]:
        cash = max(cash, hold + p)   # sell or rest in cash
        hold = max(hold, cash - p)   # buy or keep holding
    return cash


if __name__ == "__main__":
    prices = [7, 1, 5, 3, 6, 4]
    print(max_profit_unlimited_greedy(prices))  # 7
    print(max_profit_unlimited_dp(prices))      # 7

Java

public class StockTwo {

    /** Greedy — accumulate every positive day-over-day delta. */
    public static int maxProfitGreedy(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;
    }

    /** 2-state DP — cash and hold. */
    public static int maxProfitDp(int[] prices) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int p = prices[i];
            cash = Math.max(cash, hold + p);
            hold = Math.max(hold, cash - p);
        }
        return cash;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfitGreedy(prices)); // 7
        System.out.println(maxProfitDp(prices));     // 7
    }
}

C

#include <stdio.h>

int max_profit_unlimited(int prices[], int n) {
    int profit = 0, i;
    for (i = 1; i < n; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

int main(void) {
    int prices[] = {7, 1, 5, 3, 6, 4};
    printf("%d\n", max_profit_unlimited(prices, 6)); /* 7 */
    return 0;
}

Stock II Output & Trace

Program output

Greedy delta trace for [7, 1, 5, 3, 6, 4]

Stock III — At Most 2 Transactions

Problem (LeetCode 123): At most two complete buy→sell cycles. Use four rolling states:

• buy1 — best after first buy
• sell1 — best after first sell
• buy2 — best after second buy (using profit from first cycle)
• sell2 — best after second sell (final answer)

Stock III Code (C, Java, Python)

Python

def max_profit_two_tx(prices):
    """LeetCode 123 — at most 2 transactions. O(n) time, O(1) space."""
    buy1 = buy2 = float('-inf')
    sell1 = sell2 = 0
    for p in prices:
        buy1 = max(buy1, -p)
        sell1 = max(sell1, buy1 + p)
        buy2 = max(buy2, sell1 - p)
        sell2 = max(sell2, buy2 + p)
    return sell2


if __name__ == "__main__":
    print(max_profit_two_tx([3, 3, 5, 0, 0, 3, 1, 4]))  # 6
    print(max_profit_two_tx([1, 2, 3, 4, 5]))              # 4
    print(max_profit_two_tx([7, 6, 4, 3, 1]))              # 0

Java

public class StockThree {

    /** At most 2 transactions — 4-state rolling DP. */
    public static int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE / 2;
        int buy2 = Integer.MIN_VALUE / 2;
        int sell1 = 0, 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;
    }

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{3, 3, 5, 0, 0, 3, 1, 4})); // 6
        System.out.println(maxProfit(new int[]{1, 2, 3, 4, 5}));             // 4
    }
}

C

#include <stdio.h>
#include <limits.h>

int max2(int a, int b) { return a > b ? a : b; }

int max_profit_two_tx(int prices[], int n) {
    int buy1 = INT_MIN / 2, buy2 = INT_MIN / 2;
    int sell1 = 0, sell2 = 0, i;
    for (i = 0; i < n; i++) {
        int p = prices[i];
        buy1 = max2(buy1, -p);
        sell1 = max2(sell1, buy1 + p);
        buy2 = max2(buy2, sell1 - p);
        sell2 = max2(sell2, buy2 + p);
    }
    return sell2;
}

int main(void) {
    int prices[] = {3, 3, 5, 0, 0, 3, 1, 4};
    printf("%d\n", max_profit_two_tx(prices, 8)); /* 6 */
    return 0;
}

Trace for [3, 3, 5, 0, 0, 3, 1, 4] → answer 6

Stock IV — At Most k Transactions

Problem (LeetCode 188): Generalization — at most k complete transactions.

DP when k is small: dp[t][i] = max profit using at most t transactions through day i. Rolling helper max_diff = max(max_diff, dp[t−1][i] − prices[i]) gives O(k·n) time, O(k·n) space (or O(n) with one row per transaction count).

Python — Stock IV

def max_profit_k(k, prices):
    """LeetCode 188 — at most k transactions. O(k*n) time."""
    if not prices or k == 0:
        return 0
    n = len(prices)
    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    dp = [[0] * n for _ in range(k + 1)]
    for t in range(1, k + 1):
        max_diff = -prices[0]
        for i in range(1, n):
            dp[t][i] = max(dp[t][i - 1], prices[i] + max_diff)
            max_diff = max(max_diff, dp[t - 1][i] - prices[i])
    return dp[k][n - 1]


if __name__ == "__main__":
    print(max_profit_k(2, [2, 4, 1]))           # 2
    print(max_profit_k(2, [3, 2, 6, 5, 0, 3]))  # 7

Cooldown, Fee & Other Variants

Python — Cooldown & Fee (sketch)

def max_profit_cooldown(prices):
    """LeetCode 309 — sell then rest one day before rebuy."""
    hold, sold, rest = -prices[0], 0, 0
    for p in prices[1:]:
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - p)
        sold = prev_hold + p
        rest = max(prev_rest, prev_sold)
    return max(sold, rest)


def max_profit_fee(prices, fee):
    """LeetCode 714 — fee deducted on each sell."""
    cash, hold = 0, -prices[0]
    for p in prices[1:]:
        cash = max(cash, hold + p - fee)
        hold = max(hold, cash - p)
    return cash

Greedy vs DP

• Stock I: Single pass min-price tracking — no DP table needed.
• Stock II: Greedy (sum ups) and 2-state DP always agree.
• Stock III+: State-machine DP is the standard interview framework; greedy alone fails when transaction count is limited.
• Pattern: Start with brute-force recursion → memo → compress states to O(1) rolling variables.

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify transaction rules: one share at a time? unlimited vs at-most-k? fee or cooldown?
2. Draw the cash / hold state diagram before coding.
3. Stock I: never use nested loops — O(n) min-price is expected.
4. Stock II: mention greedy first; show DP if interviewer asks for proof.
5. Stock III: write buy1, sell1, buy2, sell2 updates in order — trace [3,3,5,0,0,3,1,4].
6. Stock IV: state if k ≥ n/2 → Stock II to avoid TLE.
7. Connect to knapsack (limited resources) and jump game (greedy vs DP tradeoffs).
8. Wrong pattern: trying to find exact buy/sell days with nested loops for k transactions — use DP states instead.