Easy explanation of the tricky DP solution


  • 0
    R

    My solution is inspired from clubmaster's solution. Do give him an upvote so that his solution comes above in the list.
    Explanation:
    Since we need to get max profit from 2 sells and buys, the equation is (sell1 + sell2) - (buy1 + buy2). Now if we move around some variables, it becomes sell2 + (sell1 - buy1) - buy2 which is basically sell2 + (profit1 - buy2). Thus in the 3rd line inside for-loop, I am trying to get the maximum value left after buying the second stock. I hope the code is easily understandable now. I also struggled when I saw the clever solution by other people here.

    public class Solution {
        public int maxProfit(int[] prices) {
            
            int buy1 = Integer.MAX_VALUE;
            int profit1 = 0;
            
            int buy2 = Integer.MIN_VALUE;
            int sell2  = 0;
            
            for(int i=0; i<prices.length; i++) {
                buy1 = Math.min(buy1, prices[i]);
                profit1 = Math.max(profit1, prices[i] - buy1);
                
                buy2 = Math.max(buy2, profit1 - prices[i]);
                sell2 = Math.max(sell2, prices[i] + buy2);
            }
            
            return sell2;
        }
    }
    

  • 0
    X

    @RT42 One question , what the meaning of buy2 and sell2 in your code , I think it is different from you specified in the explanation.


  • 0
    X

    @xiaowu4 got it . The buy2 means you left when the second translation ,and sell2 means the final profit .right?


  • 0
    R

    @xiaowu4 yes sell2 is the final profit also. buy2 here contains the maximum money left with the user after he buys the second share after selling the first one.


Log in to reply
 

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