Welcome to Subscribe On Youtube
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 i^{th}
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 * 10^{4}
1 <= prices[i] < 5 * 10^{4}
0 <= fee < 5 * 10^{4}
Solutions
Solution 1: Memoization
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$.
Solution 2: Dynamic Programming
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$.
We notice that the transition of the state $f[i][]$ only depends on $f[i  1][]$ and $f[i  2][]$. Therefore, we can use two variables $f_0$ and $f_1$ to replace the array $f$, reducing the space complexity to $O(1)$.
Solution 3: Greedy
Variables
f1
: Represents the maximum profit that can be achieved up to the current day with the last operation being a buy or hold after a buy. It’s initialized toprices[0]
because if we buy the stock on the first day, our profit is negative (the cost of the stock).f2
: Represents the maximum profit that can be achieved up to the current day with the last operation being a sell or hold after a sell. It’s initialized to0
because we haven’t made any transactions yet.
Logic
The idea is to iterate through each day’s price after the first day, updating f1
and f2
to reflect the maximum profit that can be achieved up to that day.
 Updating
f1
(Buy or Hold after Buy):f1
is updated to be the maximum of itself (f1
) orf2  price
.f1
(staying in the buy state) means we are not making any new transactions; we’re just carrying forward the profit (or loss) from the previous day.f2  price
means we are considering a new buy on this day. We subtract the current day’s price fromf2
, the best profit we could have after a sell up to the previous day, to reflect the cost of this buy. This comparison ensures that
f1
represents the best profit achievable by either continuing to hold a stock or buying anew.
 Updating
f2
(Sell or Hold after Sell):f2
is updated to be the maximum of itself (f2
) orf1 + price  fee
.f2
(staying in the sell state) means we are not making any new transactions; we’re just carrying forward the profit from the previous day.f1 + price  fee
means we are considering a sell on this day. We add the current day’s price tof1
, the best profit we could have with the last operation being a buy, and subtract the transaction fee to reflect the cost of this sell. This comparison ensures that
f2
represents the best profit achievable by either continuing to hold after a sell or selling the stock.
Return Value
 After iterating through all prices,
f2
will represent the maximum profit achievable by the end of the last day, with the last operation being a sell or hold after a sell. Therefore,f2
is returned as the solution.

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; } }

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]; } };

class Solution: def maxProfit(self, prices: List[int], fee: int) > int: f1, f2 = prices[0], 0 for price in prices[1:]: f1 = max(f1, f2  price) f2 = max(f2, f1 + price  fee) return f2 ############ 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 ############ class Solution: def maxProfit(self, prices, fee): """ :type prices: List[int] :type fee: int :rtype: int """ cash = 0 hold = prices[0] for i in range(1, len(prices)): cash = max(cash, hold + prices[i]  fee) hold = max(hold, cash  prices[i]) return cash

func maxProfit(prices []int, fee int) int { f0, f1 := 0, prices[0] for _, x := range prices[1:] { f0, f1 = max(f0, f1+xfee), max(f1, f0x) } return f0 }

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; }