BestTimeToBuyAndSellStockWithTransactionFee [source code]

public class BestTimeToBuyAndSellStockWithTransactionFee {
static
/******************************************************************************/
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int state = 0, profit = 0, prev = 0;
        for (int price : prices) {
            state += price - prev;
            if (state > fee) {
                profit += state - fee;
                state = fee;
            } else if (state < 0) {
                state = 0;
            }
            prev = price;
        }
        return profit;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BestTimeToBuyAndSellStockWithTransactionFee.Solution tester = new BestTimeToBuyAndSellStockWithTransactionFee.Solution();
    }
}

虽然明确的知道是DP问题, 但是暂时还是找不到一个思路;

思考了一段时间之后, 看了一下hint, hint想给的信息其实还是很直白的, 因为这个DP问题, 你最后想要找到的是一个表格, 那么他这里给的一个信息其实就是告诉你, 要考虑root involvement: root所在的位置的这个价格, 是否参与了当前结果的构造;

这个提示还是给的挺露骨的, 不过还是有点不理解这个题目最后是什么方向走;

想了半天还是想不出来, 直接看答案了;

最后是根据那个Python解法自己改写了一个出来; 速度是12ms (100%), 非常的恐怖;

editorial

Approach #1: Dynamic Programming [Accepted]

Intuition and Algorithm

At the end of the i-th day, we maintain cash, the maximum profit we could have if we did not have a share of stock, and hold, the maximum profit we could have if we owned a share of stock.

To transition from the i-th day to the i+1-th day, we either sell our stock cash = max(cash, hold + prices[i] - fee) or buy a stock hold = max(hold, cash - prices[i]). At the end, we want to return cash. We can transform cash first without using temporary variables because selling and buying on the same day can't be better than just continuing to hold the stock.

class Solution {  
    public int maxProfit(int[] prices, int fee) {  
        int cash = 0, hold = -prices[0];  
        for (int i = 1; i < prices.length; i++) {  
            cash = Math.max(cash, hold + prices[i] - fee);  
            hold = Math.max(hold, cash - prices[i]);  
        }  
        return cash;  
    }  
}

看了半天看懂了, 只能说这个答案真的是太elegant了; 逻辑本身其实是很直接的: 站在day i:

如果我今天之后没有share, 那么我要么是继续保留之前的cash, 要么就是昨天其实是有share的, 但是我今天sell out了;
如果我今天之后有share, 那么要么是我之前就有share, 所以是保留之前的hold, 要么是今天刚刚买进. 注意这里, 我们把fee只安排在卖出的时候才承担, 所以这里没有承担fee;

这个答案的逻辑实在是太简练了; 虽然事后看起来完全是行云流水, 不过做题目的时候, 怎么想得到这样的算法的?

而且之前也做过两个stock的问题了, 但是那几题都属于是类似分析整个graph, 包括分析最值, tick这些东西得到答案的; 这里这个答案, 完全是纯粹的逻辑角度来出发, 怎么想到的?

另外, 虽然我知道DP问题当中需要考虑root involvement, 不过这里这个involvement比我想象的要复杂很多; 我一开始看到hint的时候还以为只是让我区分, root是否属于构成max profit until [root]的uptick之一; 但是这里看来, 这个答案使用的involvement并不完全是这个意思;

如果非要找到一个牵强的解释, 让我可以用一个mechanical的方法找到这个思路, 或许可以区分root的状态, 是buy in了, 还是sell out了, 还是不变, 也就是完全不参与交易? 当然, 即使这个root level decision, 其实也不是那么容易想到的; 主要还是因为我看到stock的题目脑子里就定死了只会往图形的角度去想;

自己尝试性的用这个思路去写了一下看看, 感觉写不出来, 最后你会发现你need to know一个东西: 就是share的状态, 你手上到底有没有share, 只有这样, 你才能当在假设今天有一个动作的时候, 应该去查询昨天对应哪个动作的结果;

DP算法本身的优越性就是可以做到无视所有的path, 也就是不需要去管之前的path到底来自于什么样的decision组合, 但是有时候, 就跟这一题一样, 你是需要一点额外信息的, 不可能对当前的位置只储存一个结果; 这个时候, 这个你需要知道的, 需要有区分的信息, 往往就可以存放在root involvement这个decision里面, 也就是给表格加一个维度; 这么讲不知道有没有意义;

另外一个小技巧, 看他的循环是从1开始的, 这个其实也是我们以前总结过的一个东西了, DP问题, 有时候发现初始化比较难处理, 就自己多加几个base case算了;

稍微总结一下, 他这里这个算法的思路的一个核心, 就是盯着one share of stock的状态来思考; 当然了, 这个总结本身其实是有点事后诸葛亮的;

另外, awice最后专门加的那个temporary variable的, 其实是针对这一条评论:

@immiao said in Best Time to Buy and Sell Stock with Transaction Fee:

I feel this is semantically incorrect. cash has been updated before hold = max(hold, cash - prices[i]). But luckily if cash comes from the previous cash, it's fine. If cash is from hold + prices[i] - fee, then in hold = max(hold, cash - prices[i]), cash - prices[i] equals hold + prices[i] - fee - prices[i] which equals hold - fee, which is always smaller than hold, leading to a correct result. This is tricky and misleading. It would be better to use preCash and preHold.

intermediate state in mutual assignments

因为这个人描述的这个情形就是当天同一天sell完了之后立刻就重新buy的情况; 正好, 这个情况可以被证明无关紧要; 不过他的想法是正确的, 用一个pre这样的中间量来做是最直观也最不容易错的;

这个是discussion里面一个也提到这个temp问题的解法:

@zestypanda said in C++, concise solution, O(n) time O(1) space:

The solution maintains two states:
s0 = profit having no stock  
s1 = profit having 1 stock
The code iterates through the stock prices, and updates s0, s1 respectively. The run time is O(n).
update s0 by selling the stock from s1, so s0 = max(s0, s1+p);  
update s1 by buying the stock from s0, so s1 = max(s1, s0-p-fee);

class Solution {  
public:  
    int maxProfit(vector<int>& prices, int fee) {  
        int s0 = 0, s1 = INT_MIN;   
        for(int p:prices) {  
            int tmp = s0;  
            s0 = max(s0, s1+p);  
            s1 = max(s1, tmp-p-fee);  
        }  
        return s0;  
    }  
};

@Diaoge said in C++, concise solution, O(n) time O(1) space:

The "tmp" is in fact unnecessary, though it could make the code easy to read.

If s0 is not updated on day i, then tmp == s0.
If s0 is updated on day i, then tmp != s0. Observe that s0 is updated because we sell on day i. For optimal profit, we don't buy on the same day, which means s1 is still s1.

I discard "tmp" and the code is accepted.

加上一个很tricky的小point:

@hiiwave said in C++, concise solution, O(n) time O(1) space:

Nice and concise solution! I just noticed there's one interesting fact here, which is one can put the transaction fee either in the buy side or in the sell side. In other words, the following Options are both applicable.
# Option 1  
update s0 by selling the stock from s1, so s0 = max(s0, s1+p);  
update s1 by buying the stock from s0, so s1 = max(s1, s0-p-fee);  

# Option 2  
update s0 by selling the stock from s1, so s0 = max(s0, s1+p-fee);  
update s1 by buying the stock from s0, so s1 = max(s1, s0-p);
The tricky part is, if we use the second option, we could NOT set the initial value of s1 to be INT_MIN. Instead, we should use a small enough value like -50005 as what @calyoung did. The reason is that p-fee might be less than zero and cause INT_MIN+p-fee to overflow.

Just feel it interesting hence point it out :)

一个有点意思的c解法:
@rrungta said in C++, concise solution, O(n) time O(1) space:

Similar to the above solutions in O(n), another approach in C:

int maxProfit(int* prices, int pricesSize, int fee)   
{  
    int maxProfit = 0;  
    int buyingPrice = 0;  
    int sellingPrice;  
    int  iter;  

    if (pricesSize <= 1)  
        return 0;  

    buyingPrice = prices[0] + fee;  
    sellingPrice = -1;  
    for (iter = 1; iter < pricesSize; iter++)  
    {  
        if (sellingPrice == -1)  
        {  
            if ((prices[iter] + fee) < buyingPrice)  
            {  
                buyingPrice = prices[iter] + fee;  
                continue;  
            }  

            if (prices[iter] <= buyingPrice)  
                continue;  

            sellingPrice = prices[iter];  
        }  
        else if ((prices[iter] + fee) < sellingPrice)  
        {  
            maxProfit += (sellingPrice - buyingPrice);  
            sellingPrice = -1;  
            buyingPrice = prices[iter] + fee;  
        }  
        else if (prices[iter] > sellingPrice)  
            sellingPrice = prices[iter];  
    }  

    if (sellingPrice != -1)  
        maxProfit += (sellingPrice - buyingPrice);  

    return maxProfit;  
}

他这个解法其实是有点greedy的, 他直接就是首先能buy就赶紧buy, 然后buy的价格认为有一个fee的penalty; 假如后面出现一个更低的penalized buy in price, 那么换成在这里buy; 否则, 就attemp to sell here: 注意他这里也是用了todo variable这个技巧, 这也是为什么他的名字里面带有ing;

当我们有一个TODO的buy and sell interval之后, 又看到一个价格, 假如这个价格足够低, 以至于penalized buy in price都低于selling价格, 那么之前的todo就转换成done; 但是假如现在这个价格比selling价格更高, 那么就改成to sell here;

注意他price始终是跟sellingPrice或者是buyingPrice + fee比较的;

总体来说是一个很有效的算法; 他观察到了这个penalty背后应该怎么处理;

这个解法背后的思考其实是很深刻的; 这个问题的一个比较难以处理的不确定性就是最后到底有多少次交易; 我当时思考的时候一个无法解决的uncertainty就是, 假如[1,2]可以盈利, [4,6]也可以盈利, 有没有可能最后实际上整个做一个[1,6], 或者一个更大的overarching交易更好? 他的这个解法这里给出了一个准则, 就是并不是所有可以盈利的交易都应该最后成交, 只有当sell当天之后那天的价格足够低, 那么这一天sell才没有问题, 否则, 比如2, 10, 9, 11这样的价格, 那么中间就不sell更好; 也就是要拿这里10, 9之间的差价和fee进行比较;

类似上面的这个解法, 这里是另外一个很有趣的解法:

@xmduhan said in faster than the "max" solution and very clear answer:

class Solution(object):  
    def maxProfit(self, prices, fee):  
        state = profit = 0   
        last_price = prices[0]   
        for price in prices[1:]:                    
            state += price - last_price  
            if state > fee:  
                profit += state - fee  
                state = fee  
            else:  
                if state < 0: state = 0  
            last_price = price  
        return profit

Explanation:
. state is a switch variable
. when state >= fee, all incoming positive price movement will become profit
. when state <= 0, that, all incoming negative price movement will be discarded

[python] best run : 149 ms, beats 98.92% at this time, 35%+ faster than the "max" solution.
[java] best run: 13ms, beats 97.42% at this time, 20%+ faster than the "max"

这个解法的思路跟上面的类似, 但是不完全一样; 上面的那个C解法是用todo variable来postpone一个, 直到确定知道一个交易(pair of buy and sell)确实属于optimal答案;

而这里这个Python解法的思路, 则是用一种更优雅的方式来解决;

这个是我自己在下面的回复:

Also, it would be helpful to compare the trace between [2,10,9,11], fee = 2 and [2, 10, 2, 11], fee = 2.

The idea behind the aforementioned c solution is to postpone a transaction (pair of buy and sell) until you know for sure it's good.
OP's solution, on the other hand, can be intuitively understood like, sell whenever you can profit, say at 10, and if we find later that we sold too early, as in at 9 of [2,10,9,11], the previous state = fee is like a transaction fee refund, that cancels the previous decision of sell at 10.

9 - 10 in the case of [2, 10, 9, 11] does not entirely cancel out the state = fee = 2 so this is a successful refund, and we still hold the share of stock. Future calculation of state will still include previous price differences: state = (10 - 2 - 2) + 2 + (9 - 10) = 9 - 2 at this point.

2 - 11 in the case of [2, 10, 2, 11] makes state reset to 0, thus the refund attempt is annulled.

This does not adequately explain OP's solution, but hopefully is a helpful stab.

discussion最优解是一个非常好的对stock问题的总结:

@fun4LeetCode said in Most consistent ways of dealing with the series of stock problems:

Note: this is a repost of my original post here with updated solutions for this problem (714. Best Time to Buy and Sell Stock with Transaction Fee). If you are only looking for solutions, you can go directly to each section in part II -- Applications to specific cases.

Up to this point, I believe you have finished the following series of stock problems:

121. Best Time to Buy and Sell Stock

122. Best Time to Buy and Sell Stock II

123. Best Time to Buy and Sell Stock III

188. Best Time to Buy and Sell Stock IV

309. Best Time to Buy and Sell Stock with Cooldown

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

For each problem, we've got a couple of excellent posts explaining how to approach it. However, most of the posts failed to identify the connections among these problems and made it hard to develop a consistent way of dealing with this series of problems. Here I will introduce the most generalized solution applicable to all of these problems, and its specialization to each of the six problems above.

I -- General cases

The idea begins with the following question: Given an array representing the price of stock on each day, what determines the maximum profit we can obtain?

Most of you can quickly come up with answers like "it depends on which day we are and how many transactions we are allowed to complete". Sure, those are important factors as they manifest themselves in the problem descriptions. However, there is a hidden factor that is not so obvious but vital in determining the maximum profit, which is elaborated below.

First let's spell out the notations to streamline our analyses. Let prices be the stock price array with length n, i denote the i-th day (i will go from 0 to n-1), k denote the maximum number of transactions allowed to complete, T[i][k] be the maximum profit that could be gained at the end of the i-th day with at most k transactions. Apparently we have base cases: T[-1][k] = T[i][0] = 0, that is, no stock or no transaction yield no profit (note the first day has i = 0 so i = -1 means no stock). Now if we can somehow relate T[i][k] to its subproblems like T[i-1][k], T[i][k-1], T[i-1][k-1], ..., we will have a working recurrence relation and the problem can be solved recursively. So how do we achieve that?

The most straightforward way would be looking at actions taken on the i-th day. How many options do we have? The answer is three: buy, sell, rest. Which one should we take? The answer is: we don't really know, but to find out which one is easy. We can try each option and then choose the one that maximizes our profit, provided there are no other restrictions. However, we do have an extra restriction saying no multiple transactions are allowed at the same time, meaning if we decide to buy on the i-th day, there should be 0 stock held in our hand; if we decide to sell on the i-th day, there should be exactly 1 stock held in our hand. The number of stocks held in our hand is the hidden factor mentioned above that will affect the action on the i-th day and thus affect the maximum profit.

这个也就是我自己定义的involvement, 或者说decision; 但是也不完全是? 感觉这里只是让你要注意这个state;

Therefore our definition of T[i][k] should really be split into two: T[i][k][0] and T[i][k][1], where the former denotes the maximum profit at the end of the i-th day with at most k transactions and with 0 stock in our hand AFTER taking the action, while the latter denotes the maximum profit at the end of the i-th day with at most k transactions and with 1 stock in our hand AFTER taking the action. Now the base cases and the recurrence relations can be written as:

Base cases:
T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity

感觉好像有点难记? 其实也不算. T[-1][k][0]和T[i][0][0]其实就是分别是一个正常表格的两个方向上的base, 比如horizontal和vertical的; 当然这个-1要稍微注意一下; 其实用0也行?

至于右边两个负无穷, 是因为第三个坐标在最开始取1很不合理, 所以这里给一个负无穷? 不知道这样解释是否合理;

为什么用负无穷, 这个可以用NLP上课的时候学到的semiring的理论来理解! 其实DP问题最后选择的就是一个path; 从[..][..][1]开始的path应该永远不被选择, 那么我们怎么保证这一个, 只要按照之前semiring的观点, 让这些path的weight无限小就行了;

Recurrence relation:
T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i])

For the base cases, T[-1][k][0] = T[i][0][0] = 0 has the same meaning as before while T[-1][k][1] = T[i][0][1] = -Infinity emphasizes the fact that it is impossible for us to have 1 stock in hand if there is no stock available or no transactions are allowed.

For T[i][k][0] in the recurrence relations, the actions taken on the i-th day can only be rest and sell, since we have 0 stock in our hand at the end of the day. T[i-1][k][0] is the maximum profit if action rest is taken, while T[i-1][k][1] + prices[i] is the maximum profit if action sell is taken. Note that the maximum number of allowable transactions remains the same, due to the fact that a transaction consists of two actions coming as a pair -- buy and sell. Only action buy will change the maximum number of transactions allowed (well, there is actually an alternative interpretation, see my comment below).

他说的这个comment:
@fun4LeetCode said in Most consistent ways of dealing with the series of stock problems:

@0x0101 Well, I'm just surprised to know that you don't need to save the values of T_ik0 and T_ik1 before updating. Either the test cases did not catch this or there are new interpretations of the meanings of these two variables. But if we stick to the definitions as specified in my post, then the recurrence relations clearly say that T_ik0 and T_ik1 will depend on their values before updating. If we loop in the forward direction and do not use temporary variables, we are actually using their updated values, which goes against the recurrence relations. However, this would not be a problem if we loop in the backward direction, which is the reason I coded this way in the post.

回到正题:

For T[i][k][1] in the recurrence relations, the actions taken on the i-th day can only be rest and buy, since we have 1 stock in our hand at the end of the day. T[i-1][k][1] is the maximum profit if action rest is taken, while T[i-1][k-1][0] - prices[i] is the maximum profit if action buy is taken. Note that the maximum number of allowable transactions decreases by one, since buying on the i-th day will use one transaction, as explained above.

To find the maximum profit at the end of the last day, we can simply loop through the prices array and update T[i][k][0] and T[i][k][1] according to the recurrence relations above. The final answer will be T[i][k][0] (we always have larger profit if we end up with 0 stock in hand).

II -- Applications to specific cases

The aforementioned six stock problems are classified by the value of k, which is the maximum number of allowable transactions (the last two also have additional requirements such as "cooldown" or "transaction fee"). I will apply the general solution to each of them one by one.

Case I: k = 1

For this case, we really have two unknown variables on each day: T[i][1][0] and T[i][1][1], and the recurrence relations say:

T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], T[i-1][0][0] - prices[i]) = max(T[i-1][1][1], -prices[i])

where we have taken advantage of the base caseT[i][0][0] = 0 for the second equation.

It is straightforward to write the O(n) time and O(n) space solution, based on the two equations above. However, if you notice that the maximum profits on the i-th day actually only depend on those on the (i-1)-th day, the space can be cut down to O(1). Here is the space-optimized solution:
public int maxProfit(int[] prices) {  
    int T_i10 = 0, T_i11 = Integer.MIN_VALUE;  

    for (int price : prices) {  
        T_i10 = Math.max(T_i10, T_i11 + price);  
        T_i11 = Math.max(T_i11, -price);  
    }  

    return T_i10;  
}

注意看, 他这里的初始化是在-1位置开始的, 不是0;

Now let's try to gain some insight of the solution above. If we examine the part inside the loop more carefully, T_i11 really just represents the maximum value of the negative of all stock prices up to the i-th day, or equivalently the minimum value of all the stock prices. As for T_i10, we just need to decide which action yields a higher profit, sell or rest. And if action sell is taken, the price at which we bought the stock is T_i11, i.e., the minimum value before the i-th day. This is exactly what we would do in reality if we want to gain maximum profit. I should point out that this is not the only way of solving the problem for this case. You may find some other nice solutions here.

Case II: k = +Infinity

If k is positive infinity, then there isn't really any difference between k and k - 1 (wonder why? see my comment below), which implies T[i-1][k-1][0] = T[i-1][k][0] and T[i-1][k-1][1] = T[i-1][k][1]. Therefore, we still have two unknown variables on each day: T[i][k][0] and T[i][k][1] with k = +Infinity, and the recurrence relations say:

这个是上面说的comment:

@fun4LeetCode said in Most consistent ways of dealing with the series of stock problems:

@cs.pro Hi cs.pro. Sorry for the confusion. So there are two interpretations here. First from a mathematical point of view, limit(k) is the same as limit(k-1) when k approaches +infinity. Second, more relevant to this problem, as I said for the case of arbitrary k, when k is sufficiently large, the maximum profits will on longer depend on k but be bound by the number of available stocks. This means if k goes to +infinity, the profits won't change if you increase or decrease the value of k, that is, T[i][k][0] will be the same as T[i][k-1][0] and T[i][k][1] the same as T[i][k-1][1]. Hope this clarifies things a little bit.

回到正题:

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k-1][0] - prices[i]) = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

where we have taken advantage of the fact that T[i-1][k-1][0] = T[i-1][k][0] for the second equation. The O(n) time and O(1) space solution is as follows:
public int maxProfit(int[] prices) {  
    int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;  

    for (int price : prices) {  
        int T_ik0_old = T_ik0;  
        T_ik0 = Math.max(T_ik0, T_ik1 + price);  
        T_ik1 = Math.max(T_ik1, T_ik0_old - price);  
    }  

    return T_ik0;  
}

注意看这里的代码, 就算是真的要cache, 也只要cache一个就行了, 不用傻乎乎的两个都cache, 虽然不会有坏处;

(Note: The caching of the old values of T_ik0, that is, the variable T_ik0_old, is unnecessary. Special thanks to 0x0101 and elvina for clarifying this.)

这个是下面他们对这个问题的讨论:

@fun4LeetCode said in Most consistent ways of dealing with the series of stock problems:

@elvina Hi elvina. NICE ONE for the explanation. This same reasoning can be applied to the general case so that we can loop k in forward direction while at the same time get rid of the caching.

First here is the piece of code demonstrating looping in forward direction:
for (int price : prices) {  
    for (int j = 1; j <= k; j++) {  
        T_ik0[j] = Math.max(T_ik0[j], T_ik1[j] + price);  
        T_ik1[j] = Math.max(T_ik1[j], T_ik0[j - 1] - price);  
    }  
}
Updating of T_ik0[j] is okay since we were using the old value of T_ik1[j]. But for T_ik1[j], we were actually using the updated value of T_ik0[j-1]. This is possible because, as you said, there are two cases when updating T_ik0[j-1]:

Case 1: T_ik0[j-1] >= T_ik1[j-1] + price

Case 2: T_ik0[j-1] < T_ik1[j-1] + price

For Case 1, T_ik0[j-1] remains unchanged therefore updating T_ik1[j] will use its old value, as we should do.

For Case 2, it implies T_ik0[j-1] - price < T_ik1[j-1]. Also note that we have T_ik1[j-1] <= T_ik1[j] (intuitively if all other factors are fixed, the maximum profit will go non-decreasingly with increasing number of allowable transactions). Therefore we have T_ik0[j-1] - price < T_ik1[j-1] <= T_ik1[j] and the max function will always be evaluated to T_ik1[j], which means the updated value of T_ik0[j-1] won't contribute in this case.

Now if k = +Infinity, then T_ik1[j-1] <= T_ik1[j] becomes T_ik1[j-1] == T_ik1[j], and the above reasoning will be equivalent to yours.

@0X0101 Hello 0X0101. The caching of the old values is indeed unnecessary. You can check elvina's explanation above and the one here. Thanks to both you guys for making this clear.

回到正题

This solution suggests a greedy strategy of gaining maximum profit: as long as possible, buy stock at each local minimum and sell at the immediately followed local maximum. This is equivalent to finding increasing subarrays in prices (the stock price array), and buying at the beginning price of each subarray while selling at its end price. It's easy to show that this is the same as accumulating profits as long as it is profitable to do so, as demonstrated in this post.

Case III: k = 2

Similar to the case where k = 1, except now we have four variables instead of two on each day: T[i][1][0], T[i][1][1], T[i][2][0], T[i][2][1], and the recurrence relations are:

T[i][2][0] = max(T[i-1][2][0], T[i-1][2][1] + prices[i])
T[i][2][1] = max(T[i-1][2][1], T[i-1][1][0] - prices[i])
T[i][1][0] = max(T[i-1][1][0], T[i-1][1][1] + prices[i])
T[i][1][1] = max(T[i-1][1][1], -prices[i])

注意看这四个算式, 这个题目限制的是transaction的次数, 那么你要知道, 一个transaction包含一个buy, 也包含一个sell; 你这个transaction计数, 就应该跟我们这题的fee一样, 只在buy或者sell当中的一个进行计数. 这里他选择的方法是在buy的时候才计数, 这也是为什么只有buy操作的时候, index2才上升;

事实上, 评论里居然有人提到同样的问题, 这个是作者的回答:

@fun4LeetCode said in Most consistent ways of dealing with the series of stock problems:

@tzzz117 Hello tzzz117. Theoretically you could use the following recurrence relations:

T[i][k][0] = max(T[i-1][k][0], T[i-1][k-1][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

which then means selling a stock takes one transaction while buying will not. In my post, I used the other interpretation which says buying a stock takes one transaction while selling will not.

We have these two interpretations due to the fact that each transaction is characterized by two actions coming as a pair -- buy and sell and there cannot be other actions interleaving between those two because of the "no multiple transactions" constraint.

where again we have taken advantage of the base caseT[i][0][0] = 0 for the last equation. The O(n) time and O(1) space solution is as follows:
public int maxProfit(int[] prices) {  
    int T_i10 = 0, T_i11 = Integer.MIN_VALUE, T_i20 = 0, T_i21 = Integer.MIN_VALUE;  

    for (int price : prices) {  
        T_i20 = Math.max(T_i20, T_i21 + price);  
        T_i21 = Math.max(T_i21, T_i10 - price);  
        T_i10 = Math.max(T_i10, T_i11 + price);  
        T_i11 = Math.max(T_i11, -price);  
    }  

    return T_i20;  
}
which is essentially the same as the one given here.

Case IV: k is arbitrary

This is the most general case so on each day we need to update all the maximum profits with different k values corresponding to 0 or 1 stocks in hand at the end of the day. However, there is a minor optimization we can do if k exceeds some critical value, beyond which the maximum profit will no long depend on the number of allowable transactions but instead will be bound by the number of available stocks (length of the prices array). Let's figure out what this critical value will be.

A profitable transaction takes at least two days (buy at one day and sell at the other, provided the buying price is less than the selling price). If the length of the prices array is n, the maximum number of profitable transactions is n/2 (integer division). After that no profitable transaction is possible, which implies the maximum profit will stay the same. Therefore the critical value of k is n/2. If the given k is no less than this value, i.e., k >= n/2, we can extend k to positive infinity and the problem is equivalent to Case II.

The following is the O(kn) time and O(k) space solution. Without the optimization, the code will be met with TLE for large k values.
public int maxProfit(int k, int[] prices) {  
    if (k >= prices.length >>> 1) {  
        int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;  

        for (int price : prices) {  
            int T_ik0_old = T_ik0;  
            T_ik0 = Math.max(T_ik0, T_ik1 + price);  
            T_ik1 = Math.max(T_ik1, T_ik0_old - price);  
        }  

        return T_ik0;  
    }  

    int[] T_ik0 = new int[k + 1];  
    int[] T_ik1 = new int[k + 1];  
    Arrays.fill(T_ik1, Integer.MIN_VALUE);  

    for (int price : prices) {  
        for (int j = k; j > 0; j--) {  
            T_ik0[j] = Math.max(T_ik0[j], T_ik1[j] + price);  
            T_ik1[j] = Math.max(T_ik1[j], T_ik0[j - 1] - price);  
        }  
    }  

    return T_ik0[k];  
}
The solution is similar to the one found in this post. Here I used backward looping for the T array to avoid using temporary variables. It turns out that it is possible to do forward looping without temporary variables, too.

Case V: k = +Infinity but with cooldown

This case resembles Case II very much due to the fact that they have the same k value, except now the recurrence relations have to be modified slightly to account for the "cooldown" requirement. The original recurrence relations for Case II are given by

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

But with "cooldown", we cannot buy on the i-th day if a stock is sold on the (i-1)-th day. Therefore, in the second equation above, instead of T[i-1][k][0], we should actually use T[i-2][k][0] if we intend to buy on the i-th day. Everything else remains the same and the new recurrence relations are

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-2][k][0] - prices[i])

And here is the O(n) time and O(1) space solution:
public int maxProfit(int[] prices) {  
    int T_ik0_pre = 0, T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;  

    for (int price : prices) {  
        int T_ik0_old = T_ik0;  
        T_ik0 = Math.max(T_ik0, T_ik1 + price);  
        T_ik1 = Math.max(T_ik1, T_ik0_pre - price);  
        T_ik0_pre = T_ik0_old;  
    }  

    return T_ik0;  
}
dietpepsi shared a very nice solution here with thinking process, which turns out to be the same as the one above.

Case VI: k = +Infinity but with transaction fee

Again this case resembles Case II very much as they have the same k value, except now the recurrence relations need to be modified slightly to account for the "transaction fee" requirement. The original recurrence relations for Case II are given by

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

Since now we need to pay some fee (denoted as fee) for each transaction made, the profit after buying or selling the stock on the i-th day should be subtracted by this amount, therefore the new recurrence relations will be either

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i])
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i] - fee)

or

T[i][k][0] = max(T[i-1][k][0], T[i-1][k][1] + prices[i] - fee)
T[i][k][1] = max(T[i-1][k][1], T[i-1][k][0] - prices[i])

Note we have two options as for when to subtract the fee. This is because (as I mentioned above) each transaction is characterized by two actions coming as a pair -- buy and sell. The fee can be paid either when we buy the stock (corresponds to the first set of equations) or when we sell it (corresponds to the second set of equations). The following are the O(n) time and O(1) space solutions corresponding to these two options, where for the second solution we need to pay attention to possible overflows.

Solution I -- pay the fee when buying the stock:
public int maxProfit(int[] prices, int fee) {  
    int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;  

    for (int price : prices) {  
        int T_ik0_old = T_ik0;  
        T_ik0 = Math.max(T_ik0, T_ik1 + price);  
        T_ik1 = Math.max(T_ik1, T_ik0_old - price - fee);  
    }  

    return T_ik0;  
}
Solution II -- pay the fee when selling the stock:
public int maxProfit(int[] prices, int fee) {  
    long T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;  

    for (int price : prices) {  
        long T_ik0_old = T_ik0;  
        T_ik0 = Math.max(T_ik0, T_ik1 + price - fee);  
        T_ik1 = Math.max(T_ik1, T_ik0_old - price);  
    }  

    return (int)T_ik0;  
}

注意看, 这里应用他的这个方法, 最后在两个位置扣fee都可以, 而且不用使用之前提到过的那个特殊的负值的技巧;

III -- Summary

In summary, the most general case of the stock problem can be characterized by three factors, the ordinal of the day i, the maximum number of allowable transactions k and the number of stocks in our hand at the end of the day. I have shown the recurrence relations for the maximum profits and their termination conditions, which leads to the O(nk) time and O(k) space solution. The results are then applied to each of the six cases, with the last two using slightly modified recurrence relations due to the additional requirements. I should mention that peterleetcode also introduced a nice solution here which generalizes to arbitrary k values. If you have a taste, take a look.

Hope this helps and happy coding!

这个文章总体的解释还是很好的, 不过一个不太清晰的地方就是当k等于正无穷的时候他的解释; 我个人认为很直观的, 如果k本身是没有限制的, 那么直接就不需要这个index; 但是他的解释似乎更弯弯绕一些; 下面还有一些其他人尝试性解释这个问题, 但是我感觉解释的都不算很好;

另外一个discussion最优解:

@DonaldTrump said in Java simple DP solutions. O(n):

This problem is just like the other stock problems.
At given day, we can do 1 out of 4 things:

buy stock

hold stock

do nothing with empty portfolio

sell stock

We have 4 arrays with the length of # of the days, recording the max profit at given day if we do given operation.

Here is the code:

class Solution {  
    public int maxProfit(int[] prices, int fee) {  
        if(prices.length <= 1) return 0;  
        int[] buy = new int[prices.length];  
        int[] hold = new int[prices.length];  
        int[] skip = new int[prices.length];  
        int[] sell = new int[prices.length];  
        // the moment we buy a stock, our balance should decrease  
        buy[0] = 0 - prices[0];   
        // assume if we have stock in the first day, we are still in deficit  
        hold[0] = 0 - prices[0];  
        for(int i = 1; i < prices.length; i++){  
            // We can only buy on today if we sold stock  
            // or skipped with empty portfolio yesterday  
            buy[i] = Math.max(skip[i-1], sell[i-1]) - prices[i];   
            // Can only hold if we bought or already holding stock yesterday  
            hold[i] = Math.max(buy[i-1], hold[i-1]);  
            // Can skip only if we skipped, or sold stock yesterday  
            skip[i] = Math.max(skip[i-1], sell[i-1]);  
            // Can sell only if we bought, or held stock yesterday  
            sell[i] = Math.max(buy[i-1], hold[i-1]) + prices[i] - fee;  
        }  
        // Get the max of all the 4 actions on the last day.  
        int max = Math.max(buy[prices.length - 1], hold[prices.length - 1]);  
        max = Math.max(skip[prices.length - 1], max);  
        max = Math.max(sell[prices.length - 1], max);  
        return Math.max(max, 0);  
    }  
}

Now, you guys believe I have a higher IQ than Rex right?

略微有点啰嗦, 但是总体的思路应该还是类似的;

Problem Description

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.

Difficulty:Medium
Total Accepted:9.4K
Total Submissions:21.4K
Contributor:Jiachen_
Companies
facebookbloomberg
Related Topics
arraydynamic programminggreedy
Similar Questions
Best Time to Buy and Sell Stock II

Hint 1
Consider the first K stock prices. At the end, the only legal states are that you don't own a share of stock, or that you do. Calculate the most profit you could have under each of these two cases

LC714 BestTimeToBuyAndSellStockWithTransactionFee

BestTimeToBuyAndSellStockWithTransactionFee [source code]

editorial

Approach #1: Dynamic Programming [Accepted]

intermediate state in mutual assignments

Problem Description

results matching ""

No results matching ""