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

&#x20;[**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/description/)

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[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.
```

**Note:**

`0 < prices.length <= 50000`.

`0 < prices[i] < 50000`.

`0 <= fee < 50000`.

***My Solutions:***

因为涉及两种状态，所以不能和#122一样用贪心算法。

每一天可能进行卖旧股或者买新股的操作，必须先卖旧股再买新股。因此，需要建立两个动态规划数组：sold和hold。`sold[i]`表示，如果第i天出售股票，可以得到的最大利润。`hold[i]`表示，如果第i天保留股票，可以得到的最大利润。

`sold[i]`有两个状态，选择1或2中的最大值：

1. 不卖股票，保持前一天也就是`sold[i-1]`的售出利润
2. 在i天卖掉股票，总利润是前一天手里有股票的利润+今天卖出价格-交易费

sold\[i] = max(sold\[i-1], hold\[i - 1] + prices\[i] - fee);

`hold[i]`也有两个状态，选择1或2中的最大值：

1. 保持前一天也就是hold\[i-1]的利润
2. 在i天购入新股，总利润是昨天股票卖了的利润减去今天再买入的价格

hold\[i]=max(hold\[i-1],sold\[i−1]−prices\[i])

简化一下可以只用两个变量记录变化。利润记做cash，所以一开始cash是0，第0天时如果hold（买）股票，hold=-prices\[0]。

从第i天开始，手上的现金是不变、或者hold的值+卖出股票-fee。持有的股票利润是不变，或者用手上的现金买新股。最后返回最大的利润也就是手上的现金。

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