Simple C++ solution, O(n) Time and O(1) space complexity


  • 1
    A
    class Solution {
        vector<int> price;
    public:
        int maxProfit(vector<int> &prices) {
            
            int n = prices.size(),i,temp,max_profit=INT_MIN;
            if(n<=1)
            return 0;
            temp = prices[n-1];
    
            for(i=n-2;i>=0;i--)
            {
                if(prices[i]>temp)
                temp = prices[i];
                //here, temp -> max. selling price possible at time = i 
    
                prices[i] = temp - prices[i];
                //Now, prices[i] will store the max. profit if the stock was bought at time = i
    
                //updating max. profit.
                if(prices[i]>max_profit)
                max_profit = prices[i];
            }
            return max_profit;
        }
    };

Log in to reply
 

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