2ms Java DP Solution


  • 47
    L

    Sorry for my poor English

    public int maxProfit(int[] prices) {
        // these four variables represent your profit after executing corresponding transaction
        // in the beginning, your profit is 0. 
        // when you buy a stock ,the profit will be deducted of the price of stock.
        int firstBuy = Integer.MIN_VALUE, firstSell = 0;
        int secondBuy = Integer.MIN_VALUE, secondSell = 0;
    
        for (int curPrice : prices) {
            if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
            if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
            if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
            if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
        }
        
        return secondSell; // secondSell will be the max profit after passing the prices
    }

  • 0
    Y

    How do you figure it out ?


  • 2
    M

    Great one..my question is same..how do you guys figure it out? Is there any proper way of thinking and solving this types of problems?


  • 0
    Z

    who can explain this solutions in detail?


  • 1
    Z

    I really love this solution. It's easier to understand than DP solution.


  • 0
    S

    @zachary8832 I am always trying to use DP algorithm, but unfortunately memory exceeds the limit. Could you please explain this solution in detail for me? thanks in advance.


  • 0

    How do you come up with this solution? Can you give readers some inspiration?


  • 3
    B

    Try to explain this solution

    public int maxProfit(int[] prices) {
        // these four variables represent your profit after executing corresponding transaction
        // in the beginning, your profit is 0. 
        // when you buy a stock ,the profit will be deducted of the price of stock.
        int firstBuy = Integer.MIN_VALUE, firstSell = 0;
        int secondBuy = Integer.MIN_VALUE, secondSell = 0;
    
        
        // (-firstBuy) is min value beteen [0, curPrice.index], firstBuy itself is a negative value
        
        // (firstSell) is max profit between [0, current.index], before update it is max profit between [0, current.index-1], after update is max(firstSell.before, curPrice + firstBuy(e.g. - minValue[0, curPrice.index]))
        
        // (secondBuy) is max profit between [0,curPrice.index] under seen prices if you hold/buy a stock between[0, curPrice.index] and haven't sell it yet.
        
        // (secondSell) is max profit between [0,curPrice.index] under seen prices if you buy a second stock between [0,curPrice.index];
        
        for (int curPrice : prices) {
            if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
            if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
            if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
            if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
        }
        
        return secondSell; // secondSell will be the max profit after passing the prices
    }
    

  • 1
    X

    @lap_218 also can't understand, would you mind specifying why firstBuy should be a negative.


  • 2
    T

    @xiaowu4 after you buy the stock, your balance is reduced, right? That is why it is negative.


  • 8
    H

    I've changed it a little bit to be more straight-forward.

    public int maxProfit(int[] prices) {
        int firstBuy = Integer.MAX_VALUE;
        //profit after buy/sell
        int afterFirstSell = 0;
        int afterSecondBuy = Integer.MIN_VALUE;
        int afterSecondSell = 0;
        for (int curPrice : prices) {
            firstBuy = Math.min(firstBuy, curPrice); //for first buy price ,the lower,the better
            afterFirstSell = Math.max(afterFirstSell ,curPrice-firstBuy); // the profit after first sell ,the higher,the better
            afterSecondBuy = Math.max(afterSecondBuy ,afterFirstSell - curPrice);//the profit left after second buy,the higher,the better
            afterSecondSell = Math.max(afterSecondSell ,afterSecondBuy + curPrice); // the profit left after second sell ,the higher,the better 
        }
        return afterSecondSell ; // afterSecondSell will be the max profit ultimately
    }
    

  • 0
    J

    @Horanol I guess the firstSell does not represent sell price, but the profit after first sell. So it is better to change its name to afterFirstSell.


  • 0
    Z

    nice solution!


  • 0
    H

    @JieJackyZhang
    yeah,you're right


Log in to reply
 

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