Very simple readable C++ solution O(n) time with O(1) memory


  • -1
    W
    class Solution 
    {
    public:
        int maxProfit(vector<int>& prices) 
        {
            if (prices.empty()) return 0;
    
            int minPrice = prices[0];
            int maxProfit = 0;
            for (int i = 1; i < prices.size(); i++)
            {
                minPrice = min(prices[i], minPrice);
                maxProfit = max(prices[i] - minPrice, maxProfit);
            }
            
            return maxProfit;
        }
    };

  • 0
    N
    def maxProfit(self, ar):
        """
        :type prices: List[int]
        :rtype: int
        """
        #for i in range(len(prices)):
        if(len(ar) <= 1):
            return 0
        
            
        min_so_far = ar[0]
        max_so_far = ar[0]
        maxi_dif = 0
        for i in range(1,len(ar)):
            if ar[i] > max_so_far:
                max_so_far = ar[i]
                maxi_dif = max_so_far - min_so_far
            if ar[i] - min_so_far > maxi_dif:
                maxi_dif = ar[i] - min_so_far
            if ar[i] < min_so_far :
                min_so_far = ar[i]
        print min_so_far, max_so_far
        return maxi_dif

Log in to reply
 

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