Linear Solution C++


  • 0
    F

    At each i-th day you could be in three and only three different states:

    1. With stock
    2. Without stock and you didn't sell it yesterday
    3. Without stock and you did sell it yesterday

    So we could iterate throught the array and caclualte maximum profit at each day for all three states.

    We could notice that if there is only one day - no point to buy the stock so we could do an early return:

            if (prices.size() < 2)
                return 0;
    

    thus we start to calculate from the 2th day. First we need to initialize start values after 1st day (1st != 0 day):

            int profitWith = max(-prices[0], -prices[1]); // We need to be with stock - let's choose the cheapest 
            int profitWithoutNotSold = 0; // We didn't sold stock on 1st day - so we didn't bought stock at zero day (otherwise we end up 1st day with stock)
            int profitWithoutSold = prices[1] - prices[0]; // We did sold stock on 1st day - so we bought it on zero day
    

    Then main loop:

            for (int i = 2; i < prices.size(); ++i)
            {
                int tempWith = profitWith;
                int tempWithoutNotSold = profitWithoutNotSold;
                int tempWithoutSold = profitWithoutSold;
                
                profitWith = max(tempWith, tempWithoutNotSold - prices[i]); // don't sell or sell, but we couldn't sell if we sold yesterday
                profitWithoutNotSold = max(tempWithoutNotSold, tempWithoutSold); // take the max of two sell values and don't sell
                profitWithoutSold = tempWith + prices[i]; // sell
            }
    

    And in the end just take the maximum profit from all three states. Also we could notice that we couldn't have the maximum profit if we didn't sell the last stock, so
    it's enough to take the maximum between profitWithoutNoSold and profitWithoutSold:

     return max(profitWithoutNotSold, profitWithoutSold);
    

    Here's all the code together

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if (prices.size() < 2)
                return 0;
            
            int profitWith = max(-prices[0], -prices[1]);
            int profitWithoutNotSold = 0;
            int profitWithoutSold = prices[1] - prices[0];
            
            for (int i = 2; i < prices.size(); ++i)
            {
                int tempWith = profitWith;
                int tempWithoutNotSold = profitWithoutNotSold;
                int tempWithoutSold = profitWithoutSold;
                
                profitWith = max(tempWith, tempWithoutNotSold - prices[i]);
                profitWithoutNotSold = max(tempWithoutNotSold, tempWithoutSold);
                profitWithoutSold = tempWith + prices[i];
            }
            
            return max(profitWithoutNotSold, profitWithoutSold);
        }
    };
    

    Time Complexity: O(n)
    Space Complexity: O(1)


Log in to reply
 

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