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.买卖股票的题型总结：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/most-consistent-ways-of-dealing-with-the-series-of-stock-problems
思路：
建立两个一维数组dp来记录最大利润。
sell: 在第 i 天时并不持有任何股票时的最大利润。 buy：在第 i 天时持有股票能获得的最大利润。 initialize: 第一天时，选择持有意味着必须亏损-prices[0]。sell[0]不可能有任何利润。 transfer: 第 i 天可以选择选择继续持有之前的股票，那么hold[i] = hold[i - 1]，或者选择在不持有股票的基础上当天买入hold[i] = sell[i - 1] - prices[i] ，两者取较大。第 i 天也可以选择不持有，也有两种方式，选择在第 i 天卖出之前持有的股票 sell[i] = hold[i - 1]，或者继续不买入的状态, sell[i] = sell[i - 1]，两者取较大。 return：因为最后相同一支股票买入却不卖出没什么意义，一定是全部卖出的利润较大，可以直接返回sell的最后状态，sell.back()。
class Solution { public: int maxProfit(vector<int>& prices, int fee) { vector<int> sell(prices.size(), 0), buy = sell; buy[0] = -prices[0]; for (int i = 1; i < prices.size(); i++) { sell[i] = max(sell[i - 1], buy[i - 1] + prices[i] - fee); buy[i] = max(buy[i - 1], sell[i - 1] - prices[i]); } return sell.back(); } };思路：
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int cash = 0, hold = -prices[0]; for (int i = 1; i < prices.size(); i++) { cash = max(cash, hold + prices[i] - fee); hold = max(hold, cash - prices[i]); } return cash; } };