Easy understanding O(n) time and O(1) space solution in cpp


  • 3
    X
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.size() == 0)
                return 0;
            
            int sell_1st = 0;
            int sell_2nd = 0;
            int buy_1st = -prices[0];
            int buy_2nd = -prices[0];
            int ret = 0;
            
            for(int i = 1; i < prices.size(); ++i)
            {
                int last_sell = sell_1st;
                sell_1st = max(sell_1st,prices[i] + buy_1st);
                buy_1st = max(-prices[i],buy_1st);
                sell_2nd = max(sell_2nd,prices[i] + buy_2nd);
                buy_2nd = max(last_sell - prices[i],buy_2nd);
                ret = max(sell_1st,sell_2nd);
            }
            
            return ret;
            
        }
    };

  • 1
    J

    Brilliant solution! Just add some explanations for someone like me couldn't understand it at the first sight.

    In every loop:

    1. If engage in one transaction:

      sell_1st = max(-buy + sell) = max( -min(prices[0 to i-1]) + prices[i] )

    2. If engage in two transactions:

      sell_2nd = max sell_1st - buy again + sell again = max( max(sell_1st in prices[0 to j]) -min(prices[j+1 to i-1]) + prices[i] )

    3. Get max(sell_1st, sell_2nd)

    With python code:

    class Solution(object):
        def maxProfit(self, prices):
            prices_len = len(prices)
            if prices_len == 0:
                return 0
            
            buy_1st, sell_1st = -prices[0], 0
            buy_2nd, sell_2nd = -prices[0], 0
            max_profit = 0
            for i in range(1, prices_len):
                last_sell = sell_1st
                sell_1st = max(sell_1st, buy_1st + prices[i])
                buy_1st = max(buy_1st, -prices[i])
                sell_2nd = max(sell_2nd, buy_2nd + prices[i])
                buy_2nd = max(buy_2nd, last_sell - prices[i])
                max_profit = max(sell_1st, sell_2nd)
            return max_profit

Log in to reply
 

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