Very understandable solution by reusing Problem III idea


  • 4

    Re: A Concise DP Solution in Java

    In Problem III (At most two transaction), I try to understand and solve this problem from state machine perspective inspired by this amazing post: https://discuss.leetcode.com/topic/30680/share-my-dp-solution-by-state-machine-thinking

    Then we conclude that we can use constant variable to represent 4 states and get a very concise solution as followed.

        public int maxProfit(int[] prices) {
            int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
            for (int price : prices) {
                buy1 = Math.max(buy1, -price);
                sell1 = Math.max(sell1, buy1 + price);
                buy2 = Math.max(buy2, sell1 - price);
                sell2 = Math.max(sell2, buy2 + price);
            }
            return sell2;
        }
    

    Now for Problem IV, we can make at most K transaction rather than only two. Why not reuse the idea above? The only edge case is the first buy which has no previous sell. So here we create two int[k + 1] array to use sell[0] as a buffer region. Here is the solution.

        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];
        }
    

    Yes, that's all. While this will TLE for large test case, so it's necessary to add a special case handling to pass that. But don't be confused, the basic idea is only the piece of data above indeed.

            if (k >= prices.length / 2) { // if k >= n/2, then you can make maximum number of transactions
                int profit = 0;
                for (int i = 1; i < prices.length; i++)
                    if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
                return profit;
            }
    

  • 0
    B

    Many solutions include something like -prices[0]. Why make that value negative and why is it used?

    also why would you ever sum the buy and sell price, as in the assignment for sell 1 in you part 3 solution? It appears to me that you would only ever diff those values.

    I think I'm just missing how dp applies here. Any help? Thanks!

    It's simple, in terms of not having to type much, but it's not very intuitive?


  • 0
    V

    @benjie to answer your -price question, think of it as money that leaves your bank account. So whenever we buy, money is transferred out, hence negative. Then when you sell, you just add the price back, because money is being transferred into your bank account.


Log in to reply
 

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