C, 3mS, O(n) time, O(1) space


  • 1
    M

    This solution is based on the Best Time to Buy and Sell Stock, the one which allows at most one transaction. If we handle one additional special case, then we can use the same approach to figure out the two most profitable transactions also.

    1. First the non-special simple use case. For example -- Consider the stock prices {3, 2, 3, 5, 8, 3, 8, 2, 6}, the best transaction is (8 - 2) and the second best is (8 - 3) which is incidentally after the best one. So just run two iterative searches and we have the solution.

    2. Now the special case: Here the most profitable transaction might involve splitting of the one best transaction into two. For example, consider the set {1, 2, 4, 2, 5, 7, 2, 4, 9, 0}. One best transaction would be (9 - 1), but the two best transactions would involve dividing that into two separate trades -- (7 - 1) & (9 - 2). To figure out this split we should look for the maximum loss making transaction within this (1 - 9) range. Basic idea is that the most loss making transaction would be flanked by the two most profitable ones!!!

    alt text

    C implementation with comments is given below. This method may not be that elegant, but seems easier to grasp.

    int maxProfit(int* p, int pSize)
    {
        int min_d, max_d, dummy1, dummy2;
        int p1, p2, p3, p4, l;
    
        /* 1. Find the transaction with the maximum profit */
        p1 = MaxProfit(p, 0, pSize - 1, &max_d, &min_d);
    
        /* 2. Now find max profit on both sides of the above range
              (min_d to max_d) */
        p2 = MaxProfit(p, 0, min_d - 1, &dummy1, &dummy2);
        p3 = MaxProfit(p, max_d + 1, pSize - 1, &dummy1, &dummy2);
    
        /* 3. Find the maximum loss making transaction within the range
           min_d to max_d. The idea is that the transactions on both sides
           of the maximum loss making fall would add up to maximum profit. */
        l = MaxLoss(p, min_d, max_d, &dummy1, &dummy2);
        p4 = p1 - l + (l * 2); // calculate the profit
    
        /* Now return the larger combination. */
        p1 = (p1 + p2 > p1 + p3) ?  p1 + p2 : p1 + p3;
        return p1 > p4 ? p1 : p4;
    }
    
    int MaxProfit(int *p, int start, int end, int *max_d, int *min_d)
    {
        int i, maxp = 0, minp = start;
    
        *max_d = *min_d = start; // initialize dates to start
    
        for (i = start + 1; i <= end; ++i) {
            if (maxp < p[i] - p[minp]) { // update sell date to maximize profit
                maxp = p[i] - p[minp];
                *max_d = i;
                *min_d = minp;
            }
            minp = (p[minp] >= p[i]) ? i : minp; // update possible buy date
        }
        /* Return the value */
        return p[*max_d] - p[*min_d];
    }
    
    int MaxLoss(int *p, int start, int end, int *max_d, int *min_d)
    {
        int i, maxp = 0, mp = start;
        *max_d = *min_d = start; // initialize dates to start
    
        for (i = start + 1; i <= end; ++i) {
            if (maxp < p[mp] - p[i]) { // update sell date to maximize loss
                maxp = p[mp] - p[i];
                *max_d = mp;
                *min_d = i;
            }
            mp = (p[mp] <= p[i]) ? i : mp; // update possible buy date
        }
    
        /* Return the max loss */
        return p[*max_d] - p[*min_d];
    }
    

Log in to reply
 

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