Share my C++ DP solution,easy to understand


  • 0
    V
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int n = prices.size();
            if (n == 0 || n == 1) return 0;
            
            int profit, maxSellPrice, i;
            
            profit = 0;
            maxSellPrice = prices[n - 1];
            
            for (i = n - 1; i >= 0; --i)
            {
                profit = max ((maxSellPrice - prices[i]), profit);
                    
                if (maxSellPrice < prices[i])
                    maxSellPrice = prices[i];
            }
    
            return profit;
        }
    };
    

    The same:

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

Log in to reply
 

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