题目：买卖股票的最佳时机含手续费

• 给定一个整数数组prices，其中第i个元素代表了第i天的股票价格 ；非负整数fee代表了交易股票的手续费用。
• 你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
• 返回获得利润的最大值。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意:

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

来源：力扣（LeetCode）第714题

链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

分析：

• 这道题看似很难，但只要找准状态，就变得很简单。
• 我们把数组长度理解为天数，我们每一天只要知道两个状态。
• cost：手里没有股票的最大利润
• hold：手里有股票的最大利润
• 如果当天是cost，有两种可能，一种是昨天手里就没股票，今天依然不买。第二种昨天手里有股票，今天卖了。
• 如果当天是hold，也有两种可能，一种昨天手里有股票，今天不操作，另一种昨天手里没股票，今天买了。
• 你每次都要选择最优的情况，比如昨天100.今天就10块，如果你手里有股票，那你肯定不会卖。

代码：

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

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        cash, hold = 0, -prices[0]
        for i in range(1, len(prices)):
            cash = max(cash, prices[i] + hold - fee)
            hold = max(hold, cash - prices[i])
        return cash

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)