☕ DSA Java Articles

Topics › Dynamic Programming › DP on Stocks

Best time to buy and sell stock with transaction fees

Medium TUF ID 305 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

prices[i] is the price of a stock on day i, and fee is a fixed charge paid for every completed transaction (one buy plus one sell). You may make as many transactions as you like, holding at most one share at a time. Return the maximum profit after fees.

Constraints: 1 ≤ n ≤ 5 × 10^4, 1 ≤ prices[i] < 5 × 10^4, 0 ≤ fee < 5 × 10^4. The Java file also accepts an empty array.

Example 1

prices = [1, 3, 2, 8, 4, 9], fee = 2
answer = 8          // buy 1, sell 8: 7 - 2 = 5; buy 4, sell 9: 5 - 2 = 3

Example 2

prices = [1, 3, 7, 5, 10, 3], fee = 3
answer = 6          // one long trade 1 -> 10 pays the fee once: 9 - 3 = 6

In Example 2, two trades 1 → 7 and 5 → 10 earn 6 + 5 = 11 before fees, but pay 6 in fees, leaving 5. One long trade pays the fee only once and earns 6. The fee makes the number of trades matter, which is why the “sum of all rises” greedy breaks and the DP is needed.

Approach 1: Recursion

Intuition. The state is the Stock II state: f(i, canBuy) is the best profit from day i onward, where canBuy = 1 means no share is held. The fee is charged once per transaction, so attach it to exactly one of the two moves. Attaching it to the sell is natural: a sale brings in prices[i] - fee.

A share bought but never sold pays no fee, but it also never returns its price, so such plans are never optimal; the base case needs no special handling.

Algorithm.

  1. If i == n, return 0.
  2. Apply the buy or sell recurrence; subtract fee on the sell.
static int recursive(int[] prices, int fee) {
    return solve(0, 1, prices, fee);
}

static int solve(int i, int canBuy, int[] prices, int fee) {
    if (i == prices.length) return 0;
    if (canBuy == 1) {
        return Math.max(-prices[i] + solve(i + 1, 0, prices, fee),      // buy today
                        solve(i + 1, 1, prices, fee));                  // skip
    }
    return Math.max(prices[i] - fee + solve(i + 1, 1, prices, fee),     // sell today and pay the fee
                    solve(i + 1, 0, prices, fee));                      // keep holding
}

Complexity. Time O(2^n), space O(n) stack.

Approach 2: Memoization

Intuition. There are 2n states. Cache each answer; -1 is a safe “not computed” marker because doing nothing always earns 0, so no state is negative.

static int memoization(int[] prices, int fee) {
    int[][] dp = new int[prices.length][2];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(0, 1, prices, fee, dp);
}

static int memo(int i, int canBuy, int[] prices, int fee, int[][] dp) {
    if (i == prices.length) return 0;
    if (dp[i][canBuy] != -1) return dp[i][canBuy];
    int best;
    if (canBuy == 1) best = Math.max(-prices[i] + memo(i + 1, 0, prices, fee, dp), memo(i + 1, 1, prices, fee, dp));
    else best = Math.max(prices[i] - fee + memo(i + 1, 1, prices, fee, dp), memo(i + 1, 0, prices, fee, dp));
    return dp[i][canBuy] = best;
}

Complexity. Time O(n), space O(n) plus O(n) stack. With n = 5 × 10^4, recursion this deep may overflow Java’s default stack, so the next two versions are the practical ones.

Approach 3: Tabulation

Intuition. Row i reads only row i + 1. Fill from i = n - 1 down to 0; row n is the zero base case.

Algorithm.

  1. dp[n + 1][2], all zero.
  2. For i from n - 1 down to 0:
    • dp[i][1] = max(-prices[i] + dp[i + 1][0], dp[i + 1][1])
    • dp[i][0] = max(prices[i] - fee + dp[i + 1][1], dp[i + 1][0])
  3. Return dp[0][1].
static int tabulation(int[] prices, int fee) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2];                     // dp[n][*] = 0
    for (int i = n - 1; i >= 0; i--) {
        dp[i][1] = Math.max(-prices[i] + dp[i + 1][0], dp[i + 1][1]);
        dp[i][0] = Math.max(prices[i] - fee + dp[i + 1][1], dp[i + 1][0]);
    }
    return dp[0][1];
}

Dry run on prices = [1, 3, 2, 8, 4, 9], fee = 2 (dp[i][1] = free to buy, dp[i][0] = holding):

i price dp[i][1] dp[i][0]
6 - 0 0
5 9 max(-9 + 0, 0) = 0 max(9 - 2 + 0, 0) = 7
4 4 max(-4 + 7, 0) = 3 max(4 - 2 + 0, 7) = 7
3 8 max(-8 + 7, 3) = 3 max(8 - 2 + 3, 7) = 9
2 2 max(-2 + 9, 3) = 7 max(2 - 2 + 3, 9) = 9
1 3 max(-3 + 9, 7) = 7 max(3 - 2 + 7, 9) = 9
0 1 max(-1 + 9, 7) = 8 max(1 - 2 + 7, 9) = 9

Row 3 shows the key decision: holding a share on day 3, selling at 8 (and paying the fee) then buying again at 4 gives 6 + 3 = 9, which beats holding on to sell at 9 (7). The answer is dp[0][1] = 8.

Complexity. Time O(n), space O(n).

Approach 4: Space optimised

Intuition. Only the next row is read, so two variables hold dp[i + 1][1] and dp[i + 1][0]. Compute day i into temporaries, then overwrite.

static int spaceOptimized(int[] prices, int fee) {
    int aheadBuy = 0, aheadHold = 0;                    // dp[i + 1][1], dp[i + 1][0]
    for (int i = prices.length - 1; i >= 0; i--) {
        int buy = Math.max(-prices[i] + aheadHold, aheadBuy);
        int hold = Math.max(prices[i] - fee + aheadBuy, aheadHold);
        aheadBuy = buy;
        aheadHold = hold;
    }
    return aheadBuy;
}

Complexity. Time O(n), space O(1).

Forward view. The same recurrence is often written forwards as two running values, free and hold: hold = max(hold, free - p) and free = max(free, hold + p - fee). It is the identical DP read from the left; the backward version above is kept because it follows directly from the recursion.

Edge cases and pitfalls