A simple solution with O(n) time and O(1) space


  • 16
    K

    //now we try to improve the solution above.
    //(a[i]-a[i-1])+(a[i-1]-a[i-2])=a[i]-a[i-2] which is the profits created by i and i-2
    //so we travel from the end of the array and continually calculate the differece of i and i-1,
    //we only sum those positive profits then the final results is the maximum profits

        if(prices.size()==0|| prices.size()==1) return 0;
        int max_pro=0;
        for(int i=prices.size()-1;i>0;i--){
            if(prices[i]-prices[i-1]>0) max_pro+=prices[i]-prices[i-1];
        }
        return max_pro;

  • 0
    L

    nice trick boss!!!!


  • 0
    S

    You don't need to add a if at the beginning, because if (prices.size() <= 1), for will not execute and it will return 0 finally.


Log in to reply
 

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