My 8ms O(n) cpp solution easy to understand.


  • 0
    S
    /*
    Finding local minima(buying rate) and local maxima(selling rate) and then find subsequent profits.
    */
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int n= prices.size();
            int profit=0;
            for(int i=0; i<n; i++){
                while(i< n-1 && prices[i]> prices[i+1]) i++;
                profit-= prices[i];
                while(i< n-1 && prices[i] < prices[i+1]) i++;
                profit += prices[i];
            }
            return profit;
        }
    };

  • 1
    S

    int maxProfit(int* prices, int pricesSize)
    {
    int i;
    int sum;

    for( i = pricesSize - 1; i > 0; --i )
        prices[i] -= prices[i-1];
    sum = 0;
    for( i = 1; i < pricesSize; ++i )
        if( prices[i] > 0 )
            sum += prices[i];
    
    return sum;
    

    }


Log in to reply
 

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