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

[grandyang]

 

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]);

参见代码如下：

 

解法一：

class Solution {
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时就没能使用更新前的值了，参见代码如下：

 

解法二：

class Solution {
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;
    }
};

 

类似题目：

Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock

 

参考资料：

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

https://discuss.leetcode.com/topic/107998/most-consistent-ways-of-dealing-with-the-series-of-stock-problems

 

LeetCode All in One 题目讲解汇总(持续更新中...)