Share my O(n) greedy solution


  • 0
    S
    /*
    *  greedy: get profit every increase, then you can get the total max profit;
    */
    
    int maxProfit(vector<int> &prices) {
        int n = prices.size();
        if(n <= 1) return 0;
        
        int profit = 0, dist = 0;
        for(int i = 1; i < n; i++){
            dist = prices[i] - prices[i-1];
            if(dist > 0) profit += dist;
        }
        
        return profit;
    }

  • 0
    G

    Minor detail, but the dist variable does not need to exist outside the scope of the for loop. It's better to keep variables to as limited of a scope as possible.


Log in to reply
 

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