My O(n) time O(1) space solution


  • 3
    M

    The basic idea is that we can only earn money when we have a low and high price, and the amount we make is high - low. Moreover, you only need to consider local maximum or local minimum. For example,
    in [ 3, 2, 1, 2, 3, 4 ], only "1" and "4" are valuable.

    The program starts from the first price and iterates to the end. In each "while" loop, a local min(low3) and local max(high3) are found. Assume high1, high2, low1, low2 corresponds to the buy and sell points for the 2 transactions previous to the current while loop. There can only be 3 possibilities:

    1. The 2nd transaction buys at the newly found local min(low3) and sells at local max(high3). Then the first transaction can consider buying at low2 or selling high2 in order to produce max profit.

    2. The 2nd transaction still buys at low2, but sells at newly found max( high3). The first transaction doesn't have any new points to consider because the buy point of the second transaction stays the same.

    3. Nothing changed, 1st transaction still buys at low1 and sells at high1; and the 2nd transaction still buys at low2 and sells at high2.

    Then which possibility to choose ? just compute the profit of all 3 and choose the max one.

     class Solution {
      public:
    
    void assign( int& high1, int high2, int& low1, int low2 ) {
        int r1 = high1 - low1, r2 = high2 - low2, r3 = high2 - low1;
        
        if ( r1 >= r2 && r1 >= r3 ) {
            return;
        } else {
            if ( r2 >= r3 ) {
                low1 = low2;
            }
            high1 = high2;
        }
    }
    
    int maxProfit(vector<int> &prices) {
        
        int pSize = prices.size();
        if ( pSize == 0 ) return 0;
        
        int low1 = prices[0], high1=prices[0], low2=prices[0], high2=prices[0], low3, high3;
        int cur = 1;
        int r1, r2, r3;
        bool low3Save = false;
        
        while ( cur < pSize ) {
            // update low
            while ( cur < pSize && prices[cur] <= prices[cur-1] ) cur++;
            
            if ( cur == pSize ) break;
            
            if ( low3Save ) {
                low3 = min( prices[cur-1], low3);
                low3Save = false;
            } else {
                low3 = prices[cur-1];
            }
            
            // update high
            while ( cur < pSize && prices[cur] >= prices[cur-1] ) cur++;
            high3 = prices[cur-1];
            
            r1 = high1 - low1 + high2 - low2;
            r2 = high1 - low1 + high3 - low2;
            r3 = max(max( high1-low1, high2-low2), high2-low1) + high3 - low3;
            
            if ( r1 >= r2 && r1 >= r3 ) {
                // keep low3 if it's not used
                low3Save = true;
            } else {
                if ( r3 >= r2 ) {
                    assign( high1, high2, low1, low2);
                    low2 = low3;
                }
                
                high2 = high3;
            }
        }
        
        return high1 - low1 + high2 - low2;    
    }};

  • 0
    S

    Good solution.


Log in to reply
 

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