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.
又是一道股票交易的题，之前已经有过类似的五道题了，fun4LeetCode大神的帖子做了amazing的归纳总结，有时间的话博主也写个总结。这道题跟Best Time to Buy and Sell Stock II其实最像，但是由于那道题没有交易费的限制，所以我们就无脑贪婪就可以了，见到利润就往上加。但是这道题有了交易费，所以当卖出的利润小于交易费的时候，我们就不应该卖了，不然亏了。所以这道题还是还是得用动态规划来做，按照fun4LeetCode大神的理论，本质其实是个三维dp数组，由于第三维只有两种情况，卖出和保留，而且第二维交易的次数在这道题中没有限制，所以我们用两个一维数组就可以了，sold[i]表示第i天卖掉股票此时的最大利润，hold[i]表示第i天保留手里的股票此时的最大利润。那么我们来分析递推公式，在第i天，如果我们要卖掉手中的股票，那么此时我们的总利润应该是前一天手里有股票的利润(不然没股票卖毛啊)，加上此时的卖出价格，减去交易费得到的利润总值，跟前一天卖出的利润相比，取其中较大值，如果前一天卖出的利润较大，那么我们就前一天卖了，不留到今天了。然后来看如果第i天不卖的利润，就是昨天股票卖了的利润然后今天再买入股票，得减去今天的价格，得到的值和昨天股票保留时的利润相比，取其中的较大值，如果昨天保留股票的利润大，那么我们就继续保留到今天，所以递推时可以得到：
sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee);
hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]);
参见代码如下：
解法一：
public: int maxProfit(vector<int>& prices, int fee) { vector<int> sold(prices.size(), 0), hold = sold; hold[0] = -prices[0]; for (int i = 1; i < prices.size(); ++i) { sold[i] = max(sold[i - 1], hold[i - 1] + prices[i] - fee); hold[i] = max(hold[i - 1], sold[i - 1] - prices[i]); } return sold.back(); } };
我们发现不管是卖出还是保留，第i天到利润只跟第i-1天有关系，所以我们可以优化空间，用两个变量来表示当前的卖出和保留的利润，更新方法和上面的基本相同，就是开始要保存sold的值，不然sold先更新后，再更新hold时就没能使用更新前的值了，参见代码如下：
解法二：
public: int maxProfit(vector<int>& prices, int fee) { int sold = 0, hold = -prices[0]; for (int price : prices) { int t = sold; sold = max(sold, hold + price - fee); hold = max(hold, t - price); } return sold; } };
参考资料：
https://discuss.leetcode.com/topic/107992/java-dp-solution-easy-understand
https://discuss.leetcode.com/topic/107977/c-concise-solution-o-n-time-o-1-space
本文转自博客园Grandyang的博客，原文链接：[LeetCode] Best Time to Buy and Sell Stock with Transaction Fee 买股票的最佳时间含交易费
，如需转载请自行联系原博主。
