[714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)

### 題目描述

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).

### 範例

**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^

### 解答
#### Python

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        hold, sold = float('-inf'), 0
        for price in prices:
            hold, sold = max(hold, sold - price), max(sold, hold + price - fee)
        return sold

> [name=Yen-Chi Chen][time=Fri, Jun 23, 2023]

#### C++

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        int buy = numeric_limits<int>::min();
        int sell = 0;
        for (int i = 0; i < prices.size(); i ++) {
            buy = max(buy, sell - prices[i]);
            sell = max(sell, buy + prices[i] - fee);
            // cout << prices[i] << " " << buy << " " << sell << endl;
        }
        return sell;
    }
};

> [name=Jerry Wu][time=22 June, 2023]

#### Java

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int hold = -prices[0];
        int free = 0;

        for (int i = 1; i < n; i++) {
            int temp_hold = hold;
            hold = Math.max(hold, free - prices[i]);
            free = Math.max(free, temp_hold + prices[i] - fee);
        }

        return free;
    }
}

> [name=Ron Chen][time=Fri, Jun 23, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)