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

Your are given an array of integers `prices`, for which the `i`-th element is the price of a given stock on day `i`; and a non-negative integer `fee` representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

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 = 1Selling at prices = 8Buying at prices = 4Selling at prices = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
```

Note:

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

• b'
\n\n

#### Approach #1: Dynamic Programming [Accepted]

\n

Intuition and Algorithm

\n

At the end of the `i`-th day, we maintain `cash`, the maximum profit we could have if we did not have a share of stock, and `hold`, the maximum profit we could have if we owned a share of stock.

\n

To transition from the `i`-th day to the `i+1`-th day, we either sell our stock `cash = max(cash, hold + prices[i] - fee)` or buy a stock `hold = max(hold, cash - prices[i])`. At the end, we want to return `cash`. We can transform `cash` first without using temporary variables because selling and buying on the same day can\'t be better than just continuing to hold the stock.

\n

Python

\n
`class Solution(object):\n    def maxProfit(self, prices, fee):\n        cash, hold = 0, -prices\n        for i in range(1, len(prices)):\n            cash = max(cash, hold + prices[i] - fee)\n            hold = max(hold, cash - prices[i])\n        return cash\n`
\n

Java

\n
`class Solution {\n    public int maxProfit(int[] prices, int fee) {\n        int cash = 0, hold = -prices;\n        for (int i = 1; i < prices.length; i++) {\n            cash = Math.max(cash, hold + prices[i] - fee);\n            hold = Math.max(hold, cash - prices[i]);\n        }\n        return cash;\n    }\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the number of prices.

\n
• \n
• \n

Space Complexity: , the space used by `cash` and `hold`.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'