C++ solution - O(n), three variables - beats 97%


  • 0
    A

    Generally we have 3 states:

    • we are calculating bestPriceToBuy (2nd if statement) ie. [2,1,4] -> better to buy when price is 1
    • we are calculating bestPriceToSell (3rd if statement) ie. [2,1,4,5,1] -> better to sell when price is 5
    • we are selling (1st statement) - generally if current cost of buying stock is lower that potential sell it's better to sell
    int maxProfit(vector<int>& prices, int fee) {
            int bestPriceToBuy = 10000000;
            int bestPriceToSell = 0;
            int totalProfit = 0;
    
            for (auto price: prices) {
                if (price + fee < bestPriceToSell) {
                    totalProfit += bestPriceToSell - bestPriceToBuy;
                    bestPriceToBuy = 10000000;
                    bestPriceToSell = 0;
                }
                if (price + fee < bestPriceToBuy) {
                    bestPriceToBuy = price + fee;
                }
                if ((price > bestPriceToSell) && (price - bestPriceToBuy > 0)) {
                    bestPriceToSell = price;
                }
            }
    
            if (bestPriceToSell - bestPriceToBuy > 0) {
                totalProfit += bestPriceToSell - bestPriceToBuy;
            }
    
            return totalProfit;
        }
    

    It was twice as fast as solution with max's.


Log in to reply
 

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