keetcoder

# 714. Best Time to Buy and Sell Stock with Transaction Fee

LeetCode Problem Link (opens new window)

Given an array prices, where prices[i] is the price of a given stock on the i-th day, and an integer fee representing a transaction fee, your goal is to maximize your profit. You can complete unlimited transactions, but each time you sell a stock, you must pay the transaction fee. You cannot engage in multiple transactions simultaneously (i.e., you must sell your current holding before buying again).

Return the maximum profit you can achieve.

Example 1:

  • Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
  • Output: 8

Explanation: The maximum profit can be achieved by:

  • Buying on prices[0] = 1
  • Selling on prices[3] = 8
  • Buying on prices[4] = 4
  • Selling on prices[5] = 9
  • Total profit: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

# Approach

Greedy Solution for this problem: Greedy Algorithm: Best Time to Buy and Sell Stock with Transaction Fee (opens new window)

The performance is:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Using a greedy algorithm can be tricky and error-prone. Hence, let's also look at how to solve this problem using dynamic programming.

Compared to Dynamic Programming: 0122. Best Time to Buy and Sell Stock II (Dynamic Programming) (opens new window), we just need to subtract the fee when calculating the sell operation; the code is almost identical.

The only difference is in the recurrence relation part, therefore, no need to elaborate on all five steps of dynamic programming. Let's focus on the recurrence relation.

Here is the definition of the dp array:

dp[i][0]: Maximum cash on day i if holding a stock.

dp[i][1]: Maximum cash on day i if not holding a stock.

If holding a stock on day i, dp[i][0], it can be derived from two possible states:

  • Hold the stock on the previous day, i.e., dp[i - 1][0].
  • Buy the stock on the current day, i.e., dp[i - 1][1] - prices[i].

Thus: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]).

For not holding a stock on day i, dp[i][1], it can also be derived from two states:

  • Continuing not holding the stock from the last day, i.e., dp[i - 1][1].
  • Sell the stock on the current day minus the transaction fee, i.e., dp[i - 1][0] + prices[i] - fee.

Thus: dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee).

This problem differs from Dynamic Programming: 0122. Best Time to Buy and Sell Stock II (Dynamic Programming) (opens new window) due to the additional transaction fee subtraction.

Here is the C++ code for the above analysis:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] -= prices[0]; // Holding stock
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
  • Time Complexity: O(n)
  • Space Complexity: O(n)

# Other Language Versions

# Java:

/**
 * Pay transaction fees when selling
 * @param prices
 * @param fee
 * @return
 */
public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    // 0 : holding stock (buy)
    // 1 : not holding stock (sell)
    // dp defines the maximum cash on the i-th day holding/not holding stock
    int[][] dp = new int[len][2];
    dp[0][0] = -prices[0];
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);
}

/**
 * Pay transaction fees when buying
 * @param prices
 * @param fee
 * @return
 */
public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    int[][] dp = new int[len][2];
    dp[0][0] = -prices[0] - fee;
    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
    }
    return Math.max(dp[len - 1][0], dp[len - 1][1]);
}

// Optimized to 1D array
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[] dp = new int[2];
        dp[0] = -prices[0];
        dp[1] = 0;
        for (int i = 1; i <= prices.length; i++) {
            dp[0] = Math.max(dp[0], dp[1] - prices[i - 1]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee);
        }
        return dp[1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Java

//using 2*2 array class Solution { public int maxProfit(int[] prices, int fee) { int dp[][] = new int[2][2]; int len = prices.length; //[i][0] = holding the stock //[i][1] = not holding the stock dp[0][0] = -prices[0];

    for(int i = 1; i < len; i++){
        dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
        dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i] - fee);
    }

    return dp[(len - 1) % 2][1];
}

}

# python

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0] # Holding stock
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
        return max(dp[-1][0], dp[-1][1])
1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # Maximum cash when holding stock
        hold = -prices[0] - fee
        # Maximum cash when not holding stock
        not_hold = 0
        for price in prices[1:]:
            new_hold = max(hold, not_hold - price - fee)
            new_not_hold = max(not_hold, hold + price)
            hold, not_hold = new_hold, new_not_hold
        return not_hold
1
2
3
4
5
6
7
8
9
10
11

# Go:

// Best Time to Buy and Sell Stock with Transaction Fee Dynamic Programming
// Time Complexity: O(n) Space Complexity: O(n)
func maxProfit(prices []int, fee int) int {
    n := len(prices)
    dp := make([][2]int, n)
    dp[0][0] = -prices[0]
    for i := 1; i < n; i++ {
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
    }
    return dp[n-1][1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# JavaScript:

const maxProfit = (prices, fee) => {
    let dp = Array.from(Array(prices.length), () => Array(2).fill(0));
    dp[0][0] = 0 - prices[0];
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
    }
    return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);
}
1
2
3
4
5
6
7
8
9

# TypeScript:

function maxProfit(prices: number[], fee: number): number {
    /**
        dp[i][0]: holding stock
        dp[i][1]: not holding stock
     */
    const length: number = prices.length;
    if (length === 0) return 0;
    const dp: number[][] = new Array(length).fill(0).map(_ => []);
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for (let i = 1; i < length; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return dp[length - 1][1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# C:

#define max(a, b) ((a) > (b) ? (a) : (b))

// dp[i][0] indicates maximum cash on day i if holding a stock.
// dp[i][1] indicates maximum cash on day i if not holding a stock
int maxProfit(int* prices, int pricesSize, int fee) {
    int dp[pricesSize][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for (int i = 1; i < pricesSize; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    }
    return dp[pricesSize - 1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Rust:

Greedy

impl Solution {
    pub fn max_profit(prices: Vec<i32>, fee: i32) -> i32 {
        let mut result = 0;
        let mut min_price = prices[0];
        for i in 1..prices.len() {
            if prices[i] < min_price { min_price = prices[i]; }

            // if prices[i] >= min_price && prices[i] <= min_price + fee { continue; }

            if prices[i] > min_price + fee {
                result += prices[i] - min_price - fee;
                min_price = prices[i] - fee;
            }
        }
        result
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Dynamic Programming

impl Solution {
    pub fn max_profit(prices: Vec<i32>, fee: i32) -> i32 {
        let mut dp = vec![vec![0; 2]; prices.len()];
        dp[0][0] = -prices[0];
        for (i, &p) in prices.iter().enumerate().skip(1) {
            dp[i][0] = dp[i - 1][0].max(dp[i - 1][1] - p);
            dp[i][1] = dp[i - 1][1].max(dp[i - 1][0] + p - fee);
        }
        dp[prices.len() - 1][1]
    }
}
1
2
3
4
5
6
7
8
9
10
11

Optimized Dynamic Programming

impl Solution {
    pub fn max_profit(prices: Vec<i32>, fee: i32) -> i32 {
        let (mut low, mut res) = (-prices[0], 0);
        for p in prices {
            low = low.max(res - p);
            res = res.max(p + low - fee);
        }
        res
    }
}
1
2
3
4
5
6
7
8
9
10
Last updated:: 9/4/2025, 3:19:38 PM

← 33. Stock Problems Summary →

Copyright © 2025 keetcoder