123. Best Time to Buy and Sell Stock III - cocoder39/coco39_LC GitHub Wiki

123. Best Time to Buy and Sell Stock III

simple idea is partitioning the array into two halves at different partition points, then apply 121. Best Time to Buy and Sell Stock to each halves. time complexity is O(n^2). Suppose we divide the array into [0 .. i] and [i .. n-1]. res = dp[0 .. i] + dp[i .. n-1].

we want to optimize above algorithm to O(n). say the partition point is now nums[i+1], so we need find out the relationship between dp[0 .. i] and dp[0 .. i+1], also between dp[i .. n-1] and dp[i+1 .. n-1]

  • from 0 to i, we care that if we can achieve highest profit if selling at day i, thus we need record left_min as the price to buy in.
  • from i to sz - 1, we care that if we can achieve highest profit if we buy at day i, thus we need record right_max as price to sell.

time is O(n) and space is O(n)

int maxProfit(vector<int>& prices) {
        int sz = prices.size();
        if (sz == 0) {
            return 0;
        }
        
        vector<int> left(sz); //left[i] is max profit from [0 ... i]
        int left_min = prices[0];
        left[0] = 0;
        for (int i = 1; i < sz; i++) {
            left_min = min(left_min, prices[i]);
            left[i] = max(left[i - 1], prices[i] - left_min);
        }
        
        vector<int> right(sz); //right[i] is max profit from [i ... sz - 1]
        int right_max = prices[sz - 1];
        right[sz - 1] = 0;
        for (int i = sz - 2; i >= 0; i--) {
            right_max = max(right_max, prices[i]);
            right[i] = max(right[i + 1], right_max - prices[i]);
        }
        
        int res = INT_MIN;
        for (int i = 0; i < sz; i++) {
            res = max(res, left[i] + right[i]);
        }
        return res;
    }

it can be further optimized to O(1) space.

tips:

  • the order is sell2 -> buy2 -> sell1 -> buy1 is because sell2 depends old buy2, buy2 depends old sell1, sell1 depends on old buy1.
  • in order to update buy and sell, we initialize them with minimum value they can achieve. Same as initializing INT_MIN when finding out max value from an array. sell should always be greater than 0 and buy initially would be a negative value -prices[0] (thus make it INT_MIN first so it can be updated to -prices[0]). Otherwise, we can code like code 2, making the coding not elegant.
  • return sell2 is enough since sell2 >= buy2 + prices[i] >= sell1

code 1: good

int maxProfit(vector<int>& prices) {
        int buy1 = INT_MIN; //first buy
        int sell1 = 0; //first sell
        int buy2 = INT_MIN; //second buy
        int sell2 = 0; //second sell
        
        for (int i = 0; i < prices.size(); i++) {
            sell2 = max(sell2, buy2 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy1 = max(buy1, -prices[i]);
        }
        return sell2;
    }

code 2: not good

int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }
        
        int buy1 = -prices[0]; //first buy
        int sell1 = 0; //first sell
        int buy2 = -prices[0]; //second buy
        int sell2 = 0; //second sell
        
        for (int i = 1; i < prices.size(); i++) {
            sell2 = max(sell2, buy2 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy1 = max(buy1, -prices[i]);
        }
        return max(sell1, sell2);
    }
⚠️ **GitHub.com Fallback** ⚠️