Java DP solution Easy Understand


  • 11

    Define dp array:
    hold[i] : The maximum profit of holding stock until day i;
    notHold[i] : The maximum profit of not hold stock until day i;

    dp transition function:
    For day i, we have two situations:

    1. Hold stock:
      (1) We do nothing on day i: hold[i - 1];
      (2) We buy stock on day i: notHold[i - 1] - prices[i - 1] - fee;

    2. Not hold stock:
      (1) We do nothing on day i: notHold[i - 1];
      (2) We sell stock on day i: hold[i - 1] + prices[i - 1];

    class Solution {
        public int maxProfit(int[] prices, int fee) {
            int l = prices.length;
            int[] hold = new int[l + 1]; //Hold the stock until day i;
            int[] notHold = new int[l + 1]; //Do not hold the stock until day i;
            hold[0] = Integer.MIN_VALUE;
            
            for (int i = 1; i <= l; i++) {
                hold[i] = Math.max(hold[i - 1], notHold[i - 1] - prices[i - 1] - fee);
                notHold[i] = Math.max(notHold[i - 1], hold[i - 1] + prices[i - 1]);
            }
            
            return notHold[l];
        }
    }
    

  • 7
    Z

    Great solution. A little comment:
    it could be a bit confusing on codes like
    "We buy stock on day i: notHold[i - 1] - prices[i - 1] - fee"
    prices[i-1]? Do you mean price on the previous day? Absolutely not, right?

    So what we need to pay attention here is, these two i-1 do not mean the same thing.
    The first i-1 means "the previous day", and the second i-1 does not mean the price in previous day, but because the hold and notHold array starts at 1.

    So the second i-1 is just to make sure the indices refer to the same day.
    Hope these words can relief some people's confusion.


  • 0

    @zhtpandog Great comment! Clear explanation. Thanks.


  • 0

    @FLAGbigoffer Thank you for your nice explanation.
    One qq - You consider buying (1.2) when you are already holding a stock (1). Isn't this incorrect? In my opinion, we should consider selling (2.2) when we are already holding a stock (1). So, shouldn't it be:

    hold[i] = max(hold[i-1], hold[i-1]+prices[i-1]);
    

    Could you please help us understand?


  • 0

    @BatCoder 1. Could you please explain what is (1.2), (1), (2.2) representing?

    1. Generally speaking, I define hold[i] as the maximum profit that I could obtain when I hold a stock on day i. How can I hold a stock on day i ?
      (1) Before day i, I am already holding a stock and I do nothing on day i.
      The profit is hold[i - 1].
      (2) Before day i, I don't hold any stock and I have to buy a stock on day i.
      The profit consists of threes parts:
      Part 1: I don't hold stock before day i: notHold[i - 1];
      Part 2: I have to buy stock on day i: -prices[i]; (why I used price[i-1]
      above is to make it consistent of the index in dp array.)
      Part 3: Transaction fee: -fee.
      If you have any further questions, please let me know. Thanks.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.