My 8ms O(n) cpp solution, very intuitive (Dynamic programming)


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

Log in to reply
 

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