9ms concise solution. suprisingly simple


  • 0
    J
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.empty())
                return 0;
            int* diff = new int[prices.size() - 1];
            int ret = 0;
            for(int i = 0; i < prices.size() - 1; i++){
                diff[i] = prices[i + 1] - prices[i];
                ret += diff[i] > 0?diff[i] : 0;
            }
            return ret;
        }
    };

  • 0
    S

    hey,can u explain the reason why it can be done in the way?


  • 0
    J

    noticing that You may complete "as many transactions " as you like.
    any transaction that can earn you some money is good.

    the diff array is the difference between day i+1 and day i
    if the prices is higher in day i+1, then we should do the trading. just have to find all the transactions that can earn money


  • 0
    L

    best:

        const size_t n = prices.size();
        int ans = 0;
        for (size_t i=1;i<n;i++)
            ans += max(0,prices[i]-prices[i-1]);
        return ans;

  • 0
    T

    Good. But no need to allocate "diff", as you just need the pair-wise sum.


  • 0
    J

    yes, it can be implemented simpler


Log in to reply
 

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