8ms simple C++ solution


  • -1
    H
    int maxProfit(vector<int>& prices) {
        if (0 == prices.size()) return 0;
        int sum = 0, prev = prices[0], max = INT_MIN;
        for (int i=1, size = prices.size(); i < size; ++i) {
            int curr = prices[i];
            if (curr == prev) {
                continue;
            } else if (curr > prev) { 
                sum += (curr - prev);
            } else {
                if (sum > max) max = sum; // Keep current max sum
                sum += (curr - prev);
                if (sum < 0) sum = 0; // Start over again.
                // 2,5,[3/1],18 - if [3], we keep, if [1], we start over again.
            }
            prev = curr;
        }
        if (sum > max) max = sum;
        return (max == INT_MIN) ? 0 : max;
    }

  • 0
    H
    // My 12 lines 8 ms C++ solution
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) return 0;
        int max = INT_MIN, profit = 0, prev = prices[0];
        for (int i = 1, size = prices.size(); i < size; ++i) {
            if (profit > max) { max = profit; }
            profit += (prices[i] - prev);
            if (profit < 0)   { profit = 0; } // Clear, to calc profit from this point.
            prev = prices[i];
        }
        if (profit > max) max = profit;
        return (max == INT_MIN) ? 0 : max;
    }

Log in to reply
 

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