【week9】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] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

0 < prices.length <= 50000.

0 < prices[i] < 50000.

0 <= fee < 50000.

解题报告

题意很简单，给定每天的股价和抛售的手续费，求最大收益。

刚开始看到这题我只知道要用 dp，但是没什么思路。后来受大佬点拨，发现这题其实并不难，是我想得太复杂了，老是想着抛售的策略。

由题可知，每天有两个操作：买股和卖股。那可以定义一个数组 sold[days], hold[days]，分别表示在第 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])$$

有了这个转移方程代码实现就很简单了。但是想起上课听老师讲的背包问题后，发现这个解还可以简化，因为状态转移的时候只用到了 sold[i-1] 和 hold[i-1] ，那么为什么不可以直接用两个变量把这两个值存起来呢？

事实证明是可以的。只是在初始化两个变量时，hold 要赋值为 0，而 hold 要赋值为 -prices[0]，这是为了避免第一天不会没有买股票就卖出

sold = max(0, -prices[0] + prices[0] - fee); // sold = 0

另外，更新的顺序并没有要求，如果先更新 hold，则可以理解为，先看看要不要卖掉股票，再看要不要买今天的股票；更新 sold 的话反之。

至于同时购入两支股票的情况也并不存在，因为 hold 的状态转移是 sold -> hold（无股票时买进股票） 和 hold （持有股票）。同理无股票时卖出的情况也不会有。

Solution

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size() <= 1)
            return 0;
        int sold = 0, hold = -prices[0]; 
        for(int p : prices) {
            sold = max(sold, hold + p - fee);
            hold = max(hold, sold - p);
        }
        return sold;
    }
};