Best Time to Buy and Sell Stock with Transaction Fee

LeetCode
,

第34天。

今天又没做出来，sad，同样是一道DP的题目：

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.

先理解一下题意先，大概是输入是一个表示股票价格的数组prices以及一个表示交易费用的fee,这个fee在每次交易的时候都需要支付。

然后很自然的我们会用一个profit的数组来记录，每天能达到的最大profit，然后我们也比较容易写出一个递推式：
profit[i] = max(profit[j],profit[j] + prices[i] - prices[j] -fee) for j in range(0,i)

然后就写出了一个O(n^2)的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices, int fee) {
    if (prices.size() == 0) return 0;
    vector<int> profit(prices.size(),0);
    profit[0] = 0;
    for(int i = 1;i < profit.size();i++) {
        for(int j = i-1;j>=0;j--) {
            profit[i] = max(profit[i],profit[j]);
            int t = profit[j] + prices[i] - prices[j] - fee;
            profit[i] = max(profit[i],t);
        }
    }
    return *profit.rbegin();
}

然后就时间超限了。

想了一个早上也没能解决，很好又一次被KMP的next误导了，又是打算用加快内层循环的方式去做，但是还是会出现时间超限的问题。

哎，还是来看看dicuss中的解法吧：

1
2
3
4
5
6
7
8
9
int maxProfit(vector<int>& prices, int fee) {
    int s0 = 0,s1 = INT_MIN;
    for(auto p:prices) {
        int t = s0;
        s0 = max(s0,s1+p);      //sell
        s1 = max(s1,t-p-fee);   //buy
    }
    return s0;
}

前面的解法之所以会出现超时，就是因为他的时间复杂度为O(n^2),而dicuss中的解法却是O(n)的，这里的s0和第一个方法的profit是一样的，重要的s1.

我们知道一次交易可以分为buy和sell,他们消耗一次fee，那么我们可以将这个fee归入到buy的时候，如果当前操作是buy,那么必须保证我们当前没有股票，也就是说上一次操作是sell,这里的s0就是表示没有股票的状态，s1表示是有股票的状态。

对于s0,我们想要更新它，就只有将上一个s1卖出，然后取最大值
对于s1，我们要更新它，就只有将当前股票买入，然后取最大值。

所以就得到了上面的两条式子。