Skip to content

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

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note:

  • You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
  • The transaction fee is only charged once for each stock purchase and sale.

 

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

 

Constraints:

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

Solutions

Solution 1: Memoization

Thinking

We may trade many times and pay \(fee\) on each completed sale. \(n \le 5\times 10^4\), so an unmemoized search over days repeats states.

A day has two modes: flat or holding. From flat we buy or skip; from holding we sell (minus \(fee\)) or hold. The optimum from day \(i\) in mode \(j\) depends only on those two successors.

Memoize \(dfs(i,j)\); past the last day the profit is \(0\). The answer is \(dfs(0,0)\). There are \(O(n)\) states.

We design a function \(dfs(i, j)\), which represents the maximum profit that can be obtained starting from day \(i\) with state \(j\). Here, \(j\) can take the values \(0\) and \(1\), representing not holding and holding a stock, respectively. The answer is \(dfs(0, 0)\).

The execution logic of the function \(dfs(i, j)\) is as follows:

If \(i \geq n\), there are no more stocks to trade, so we return \(0\).

Otherwise, we can choose not to trade, in which case \(dfs(i, j) = dfs(i + 1, j)\). We can also choose to trade stocks. If \(j \gt 0\), it means that we currently hold a stock and can sell it. In this case, \(dfs(i, j) = prices[i] + dfs(i + 1, 0) - fee\). If \(j = 0\), it means that we currently do not hold a stock and can buy one. In this case, \(dfs(i, j) = -prices[i] + dfs(i + 1, 1)\). We take the maximum value as the return value of the function \(dfs(i, j)\).

The answer is \(dfs(0, 0)\).

To avoid redundant calculations, we use memoization to record the return value of \(dfs(i, j)\) in an array \(f\). If \(f[i][j]\) is not equal to \(-1\), it means that we have already calculated it, so we can directly return \(f[i][j]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(prices\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

 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
class Solution {
    private Integer[][] f;
    private int[] prices;
    private int fee;

    public int maxProfit(int[] prices, int fee) {
        f = new Integer[prices.length][2];
        this.prices = prices;
        this.fee = fee;
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        if (i >= prices.length) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        int ans = dfs(i + 1, j);
        if (j > 0) {
            ans = Math.max(ans, prices[i] + dfs(i + 1, 0) - fee);
        } else {
            ans = Math.max(ans, -prices[i] + dfs(i + 1, 1));
        }
        return f[i][j] = ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int f[n][2];
        memset(f, -1, sizeof(f));
        function<int(int, int)> dfs = [&](int i, int j) {
            if (i >= prices.size()) {
                return 0;
            }
            if (f[i][j] != -1) {
                return f[i][j];
            }
            int ans = dfs(i + 1, j);
            if (j) {
                ans = max(ans, prices[i] + dfs(i + 1, 0) - fee);
            } else {
                ans = max(ans, -prices[i] + dfs(i + 1, 1));
            }
            return f[i][j] = ans;
        };
        return dfs(0, 0);
    }
};

 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
func maxProfit(prices []int, fee int) int {
    n := len(prices)
    f := make([][2]int, n)
    for i := range f {
        f[i] = [2]int{-1, -1}
    }
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i >= n {
            return 0
        }
        if f[i][j] != -1 {
            return f[i][j]
        }
        ans := dfs(i+1, j)
        if j > 0 {
            ans = max(ans, prices[i]+dfs(i+1, 0)-fee)
        } else {
            ans = max(ans, -prices[i]+dfs(i+1, 1))
        }
        f[i][j] = ans
        return ans
    }
    return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function maxProfit(prices: number[], fee: number): number {
    const n = prices.length;
    const f: number[][] = Array.from({ length: n }, () => [-1, -1]);
    const dfs = (i: number, j: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i][j] !== -1) {
            return f[i][j];
        }
        let ans = dfs(i + 1, j);
        if (j) {
            ans = Math.max(ans, prices[i] + dfs(i + 1, 0) - fee);
        } else {
            ans = Math.max(ans, -prices[i] + dfs(i + 1, 1));
        }
        return (f[i][j] = ans);
    };
    return dfs(0, 0);
}

Solution 2: Dynamic Programming

Thinking

Solution 1 is already linear, but the recursion still uses an \(O(n)\) stack and table. The same transitions can be written forward by day.

Let \(f[i][0/1]\) be the best profit after day \(i\) flat or holding. Each row comes from the previous one; the answer is \(f[n-1][0]\).

We define \(f[i][j]\) as the maximum profit that can be obtained up to day \(i\) with state \(j\). Here, \(j\) can take the values \(0\) and \(1\), representing not holding and holding a stock, respectively. We initialize \(f[0][0] = 0\) and \(f[0][1] = -prices[0]\).

When \(i \geq 1\), if we do not hold a stock at the current day, then \(f[i][0]\) can be obtained by transitioning from \(f[i - 1][0]\) and \(f[i - 1][1] + prices[i] - fee\), i.e., \(f[i][0] = \max(f[i - 1][0], f[i - 1][1] + prices[i] - fee)\). If we hold a stock at the current day, then \(f[i][1]\) can be obtained by transitioning from \(f[i - 1][1]\) and \(f[i - 1][0] - prices[i]\), i.e., \(f[i][1] = \max(f[i - 1][1], f[i - 1][0] - prices[i])\). The final answer is \(f[n - 1][0]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(prices\).

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        f = [[0] * 2 for _ in range(n)]
        f[0][1] = -prices[0]
        for i in range(1, n):
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i] - fee)
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i])
        return f[n - 1][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] f = new int[n][2];
        f[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i] - fee);
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i]);
        }
        return f[n - 1][0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int f[n][2];
        memset(f, 0, sizeof(f));
        f[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i] - fee);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);
        }
        return f[n - 1][0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maxProfit(prices []int, fee int) int {
    n := len(prices)
    f := make([][2]int, n)
    f[0][1] = -prices[0]
    for i := 1; i < n; i++ {
        f[i][0] = max(f[i-1][0], f[i-1][1]+prices[i]-fee)
        f[i][1] = max(f[i-1][1], f[i-1][0]-prices[i])
    }
    return f[n-1][0]
}

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

Solution 3: Dynamic Programming (Space Optimization)

Thinking

Day \(i\) in Solution 2 reads only day \(i-1\), so the full table is unnecessary.

Roll two scalars \(f_0,f_1\). Parallel assignment keeps the previous pair while both updates run, so the new holding state still sees the old flat profit. Space is \(O(1)\).

The transition only needs the previous day, so two variables are enough and the space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        f0, f1 = 0, -prices[0]
        for x in prices[1:]:
            f0, f1 = max(f0, f1 + x - fee), max(f1, f0 - x)
        return f0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int f0 = 0, f1 = -prices[0];
        for (int i = 1; i < prices.length; ++i) {
            int g0 = Math.max(f0, f1 + prices[i] - fee);
            f1 = Math.max(f1, f0 - prices[i]);
            f0 = g0;
        }
        return f0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int f0 = 0, f1 = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            int g0 = max(f0, f1 + prices[i] - fee);
            f1 = max(f1, f0 - prices[i]);
            f0 = g0;
        }
        return f0;
    }
};

1
2
3
4
5
6
7
func maxProfit(prices []int, fee int) int {
    f0, f1 := 0, -prices[0]
    for _, x := range prices[1:] {
        f0, f1 = max(f0, f1+x-fee), max(f1, f0-x)
    }
    return f0
}

1
2
3
4
5
6
7
8
function maxProfit(prices: number[], fee: number): number {
    const n = prices.length;
    let [f0, f1] = [0, -prices[0]];
    for (const x of prices.slice(1)) {
        [f0, f1] = [Math.max(f0, f1 + x - fee), Math.max(f1, f0 - x)];
    }
    return f0;
}

Comments