O(n)-time 8ms Accepted Solution with Detailed Explanation (C++)


  • 27

    The idea of this thread was originally proposed by @yishiluo in
    https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

    General idea:

    We use the term "valley" to denote a local minimum index of prices, and the term "peak" to denote a local maximum index of prices. Let (v1, p1) and (v2, p2) denote two successive valley-peak pairs of the prices, respectively. Consider the two cases:

    • Case 1: prices[v1] <= prices[v2] and prices[p1] <= prices[p2]. In this case, if we can conduct one transaction, we will use (v1, p2). If we can conduct two transactions, we will use (v1, p1) and (v2, p2). Equivalently, we can consider (v1, p2) as one transaction opportunity, and (v2, p1) as another transaction opportunity. The key idea is that these two original valley-peak pairs provide two transaction opportunities: (v1, p2) and (v2, p1).

    • Case 2: prices[v1] >= prices[v2] or prices[p1] >= prices[p2]. In this case, if we can conduct one transaction, we will use either (v1, p1) or (v2, p2). If we can conduct two transactions, we will use both (v1, p1) and (v2, p2). That is, these two valley-peak pairs provides two transaction opportunities: (v1, p1) and (v2, p2).

    The algorithm consists of two steps:

    • Step 1: Find all transaction opportunities and record their profits. We use a stack vps to store the valley-peak pairs of the stock prices, wherein the valley value is sorted in ascending order. (The valley value at the top of the stack is the largest.) The profit of all transaction opportunities are recorded in the vector profits. The time complexity of this step is O(n).

    • Step 2: Find the k most profitable transaction opportunities. The maximum profit we can get is the summation of the k opportunity. The time complexity of this step is O(n), too.

    Overall complexity:

    • Time: O(n)

    • Space: worse-case O(n)


    C++ code (Accepted 8ms)

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
    
            // Step 1: Find out all profit opportunities            
            vector<int> profits;
            stack<pair<int, int>> vps; // valley-peak pairs
            
            int v;
            int p = -1;
            for (;;) {
                // find next valley-peak pair
                for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
                for (p = v  ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);
                
                if (v == p) { // v==p means that both v and p reach the end of the array
                    break;
                }
                
                // Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the new-found).
                // If prices[v1] >= prices[v2], 
                // it is meaningless to combine the two transactions.
                // Save of profit of (v1, p1), and pop it out of the record.
                while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
                    profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
                    vps.pop();
                }
                
                // If prices[v1]<prices[v2] and prices[p1]<prices[p2], 
                // then it is meaningful to combine the two transactions
                // update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
                while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
                    profits.push_back(prices[vps.top().second] - prices[v]);
                    v = vps.top().first;
                    vps.pop();
                }
                
                // save the new-found valley-peak pair
                vps.emplace(v, p);
            }
            
            // save all remaining profits
            while (!vps.empty()) {
                profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
                vps.pop();
            }
            
            // Step 2: Calculate the k highest profits
            int ret;
            if (profits.size() <= k) {
                ret = accumulate(profits.begin(), profits.end(), 0);
            } else {
                nth_element(profits.begin(), profits.end() - k, profits.end());
                ret = accumulate(profits.end() - k, profits.end(), 0);
            }
            return ret;
        }
    };

  • 8

    There is a follow-up, a.k.a. Maximum Subarray III:

    Problem:
    Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.
    The number in each subarray should be contiguous. Every subarray should contain at least one number.
    Return the largest sum.

    Example: Given [-1,4,-2,3,-2,3], k=2, return 8


    O(n) Solution:

    This follow-up can be converted into "Best Time to Buy and Sell Stock IV" by simply calling the partial_sum.

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @param k: An integer denote to find k non-overlapping subarrays
         * @return: An integer denote the sum of max k non-overlapping subarrays
         */
        int maxSubArray(vector<int> nums, int k) {            
            if (count_if(nums.begin(), nums.end(), [](int x){return x>0;}) <= k) {
                nth_element(nums.begin(), nums.end()-k, nums.end());
                return accumulate(nums.end()-k, nums.end(), 0);
            }
            nums.insert(nums.begin(), 0);
            partial_sum(nums.begin(), nums.end(), nums.begin());
            return maxProfit(k, nums);
        }
        
        int maxProfit(int k, vector<int>& prices) {
    
            // Step 1: Find out all profit opportunities            
            vector<int> profits;
            stack<pair<int, int>> vps; // valley-peak pairs
    
            int v;
            int p = -1;
            for (;;) {
                // find next valley-peak pair
                for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
                for (p = v  ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);
    
                if (v == p) { // v==p means that both v and p reach the end of the array
                    break;
                }
    
                // Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the new-found).
                // If prices[v1] >= prices[v2], 
                // it is meaningless to combine the two transactions.
                // Save of profit of (v1, p1), and pop it out of the record.
                while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
                    profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
                    vps.pop();
                }
    
                // If prices[v1]<prices[v2] and prices[p1]<prices[p2], 
                // then it is meaningful to combine the two transactions
                // update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
                while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
                    profits.push_back(prices[vps.top().second] - prices[v]);
                    v = vps.top().first;
                    vps.pop();
                }
    
                // save the new-found valley-peak pair
                vps.emplace(v, p);
            }
    
            // save all remaining profits
            while (!vps.empty()) {
                profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
                vps.pop();
            }
    
            // Step 2: Calculate the k highest profits
            int ret;
            if (profits.size() <= k) {
                ret = accumulate(profits.begin(), profits.end(), 0);
            } else {
                nth_element(profits.begin(), profits.end() - k, profits.end());
                ret = accumulate(profits.end() - k, profits.end(), 0);
            }
            return ret;
        }
    
    };
    

  • 0
    P

    How can v2,p1 considered as a transaction opportunity. Because I think v2 always happens after p1.( we cannot sell stock before even buying them. ) Can you please explain?


  • 1
    Q

    I think it's a tricky point. That means for Case 2, if we split (v1, p2) into (v1, p1) and (v2, p2), we can get (p1-v2) more profits but with one more transaction, equivalently there is a transaction with (p1-v2) profits. So it should be stored into profits and be compared in Step 2, what's more, it doesn't affect later v, p comparisons because p2 is the highest peak and v1 is the lowest valley for v1 to p2.


  • 2
    F

    thanks for the explain, but it take me quite sometime to figure out the trick.
    the key point is: profit(v1, p2) + profit(v2, p1) = profit(v1, p1) + profit(v2, p2)


  • 0
    X

    @zhiqing_xiao This solution for the follow up is the best extension I've ever seen.


  • 0

    Oh, clever to use nth to reduce the time complexity to O(n)


Log in to reply
 

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