Three O(n) algorithms from different views


  • 1
    X

    Divide and Conquer: find the left, right, and crossing maximum profit, then return the maximum of the three.
    Recurrence: T(n) = 2 * T(n/2) + O(1), according to the Master method the Running time is O(n).

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if (prices.size() == 0)
                return 0;
                
            Profit maxPrft = CalculateMaxProfit(prices, 0, prices.size()-1);
            return maxPrft.maxProfit;
        }
        
    private:
        struct Profit
        {
            int maxProfit; // the max profit in current portion
            int maxPrice; // the highest price in current portion
            int minPrice; // the lowest price in current portion
            
            Profit(int profit, int highestPrice, int lowestPrice)
                : maxProfit(profit), maxPrice(highestPrice), minPrice(lowestPrice)
            {
            }
        };
        
        Profit CalculateMaxProfit(const vector<int>& prices, int startIndex, int endIndex)
        {
            if (startIndex == endIndex)
                return Profit(0, prices[startIndex], prices[startIndex]);
                
            int midIndex = (startIndex + endIndex) / 2;
            Profit left = CalculateMaxProfit(prices, startIndex, midIndex);
            Profit right = CalculateMaxProfit(prices, midIndex+1, endIndex);
            
            int maxPrft = max(left.maxProfit, right.maxProfit);
            return Profit(max(maxPrft, right.maxPrice - left.minPrice),
                        max(left.maxPrice, right.maxPrice),
                        min(left.minPrice, right.minPrice));
        }
    };
    

    Transformation: transform the question Max(A[j] - A[i]), where j > i to question
    Max((A[j] - A[j-1]) + (A[j-1]-A[j-2]) + ... + (A[i+1] - A[i])), then we can use the "53. Maximum Subarray" to solve it.

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if (prices.size() < 2)
                return 0;
                
            vector<int> priceGaps;
            for (int i = 1; i < prices.size(); i++)
                priceGaps.push_back(prices[i] - prices[i-1]);
            
            int maxPrft = 0;
            int currPrft = 0;
            for (int i = 0; i < priceGaps.size(); i++)
            {
                currPrft += priceGaps[i];
                if (currPrft > maxPrft)
                    maxPrft = currPrft;
                    
                if (currPrft < 0)
                    currPrft = 0;
            }
            
            return maxPrft;
        }
    };
    

    Dynamic Programming most guys are using:

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if (prices.size() < 2)
                return 0;
                
            int maxPrft = 0;
            int lowestPrice = prices[0];
            for (int i = 1; i < prices.size(); i++)
            {
                int currPrft = prices[i] - lowestPrice;
                if (currPrft > maxPrft)
                    maxPrft = currPrft;
                
                if (lowestPrice > prices[i])
                    lowestPrice = prices[i];
            }
            
            return maxPrft;
        }
    };

Log in to reply
 

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