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

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