Best Time to Buy and Sell Stock IV

Question

Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

public int maxProfit(int k, int[] prices) {        
    int[] buy = new int[k + 1], sell = new int[k + 1];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int price : prices) {
        for (int i = 1; i <= k; i++) {
            buy[i] = Math.max(buy[i], sell[i - 1] - price);
            sell[i] = Math.max(sell[i], buy[i] + price);
        }
    }
    return sell[k];
}

Question 1) I understand most of the solution but I'm a bit confused about the sell[i] state. For example, when we buy a stock in buy[i], it is calculated by sell[i - 1] - price which means max profit of sell from the previous day minus the cost of buying the stock today.

However, when we buy a stock in sell[i], it is buy[i] + price instead of buy[i-1]. If we want sell today, shouldn't it be max profit of buy from yesterday + today's price? So wondering why there is a lack of + 1 when calculating sell[i].

Question 2) Instead of buying or selling we can also choose to hold and do nothing where this is expressed as buy[i]/sell[i]. However, if we don't do anything today, shouldn't the number be a duplicate from the previous day? buy[i+1]/sell[i+1]. Just wondering why it's buy[i] and not buy[i-1] since in other stock problems, when you choose to do nothing, you grab the value from the previous day.

Kolmar Kolmar · Accepted Answer · 2021-03-09T17:30:10

Note that the index i goes from 1 to the number of allowed transactions k. It means that in this solution i - 1 is not the previous day, it's the previous transaction.

At the start of each external loop iteration the buy and sell arrays already store the values from the previous day. So in the internal loop before updating buy[i] and sell[i] the values at that index come from the previous day.

So the meaning of the lines in the internal loop is actually like this:

buy[i] =                  // the best funds after buying in the i-th transaction is
  Math.max(               // the max of
    buy[i],               // not buying today at all, 
                          // i.e. just copy the value from yesterday
    sell[i - 1] - price); // or buying for today's price with the funds 
                          // after selling in the **previous** transaction
sell[i] =                 // the best funds after selling in the i-th transaction is
  Math.max(               // the max of
    sell[i],              // not selling today at all, 
                          // i.e. just copy the value from yesterday
    buy[i] + price);      // or selling for today's price with the funds
                          // after buying in the **current** transaction

Note that buying and selling in one transaction in the same day is actually not a problem. The price is the same, so it means we just ignore the i-th transaction. This means that in the end sell[k] will contain the best profit after k or fewer transactions. That's fine: for example in the first example test case k = 2, prices = [2,4,1] we use only one of the 2 allowed transactions.

Best Time to Buy and Sell Stock IV

1 Answers