8ms Easy C++ Solution


  • 3

    This problem is similar to Best Time to Buy and Sell Stock. Given prices, we find the day (denoted as buy) of the first local minimum and the day (denoted as sell) of the first local maximum (note that we initialize sell to be buy + 1 each time to guarantee the transaction is valid). Then we earn the profit prices[sell] - prices[buy], after which we update buy to be sell + 1 to check for the remaining prices.

    The code is as follows.

    class Solution {
    public: 
        int maxProfit(vector<int>& prices) {
            int buy = 0, sell = 0, profit = 0, n = prices.size();
            while (buy < n && sell < n) {
                while (buy + 1 < n && prices[buy + 1] < prices[buy])
                    buy++; 
                sell = buy; 
                while (sell + 1 < n && prices[sell + 1] > prices[sell])
                    sell++;
                profit += prices[sell] - prices[buy];
                buy = sell + 1;
            }
            return profit;
        }
    };
    

  • 2
    L
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int profit = 0, buy = 0, sell = 0;
            while(buy < prices.size() && sell < prices.size())
            {
                while(prices[buy] >= prices[buy+1] && buy < prices.size()-1)
                    ++buy;
                sell = buy;
                while(prices[sell] <= prices[sell+1] && sell < prices.size()-1)
                    ++sell;
                profit += prices[sell] - prices[buy];
                buy = sell + 1;
            }
            return profit;
        }
    };

  • 0

    Hi, liuludavid. Thank you for your sharing. I have updated my code.


  • 0
    T

    Very good explanation, but the implementation could be a bit more concise. See
    https://leetcode.com/discuss/42176/three-lines-in-c-with-explanation


  • 0
    T
    This post is deleted!

  • 0

    Hi, tian.xia.568. Great solution! Thank you for your sharing! The shortest one that I have seen. Very clever to take advantage of the cancelling of neighbor numbers.


  • 0
    R

    Hi, jianchao.li.fighter, see you again! I wonder why Then the max profit in interval [a, b] is prices[j] - prices[i] if j > i or simply 0 otherwise. For example, if prices of [a,b] are {1, 4, 2, 4}, the min is 1, and the max is 4. But the max profit is (4-1 ) + (4-2) instead of (4-1). Thanks!


  • 0

    Hi, rlaoyao. Well, there are some inaccuracies in the explanation. In fact, the code will find the first local minimum and the first local maximum of [1, 4, 2, 4] which are 1 and 4 respectively: making this transaction earns profit 4 - 1 = 3. Then the code moves on to find the next local minimum and the next local maximum, which are 2 and 4 respectively: making this transaction earns profit 4 - 2 = 2. The total profit is thus (4 - 1) + (4 - 2) = 5. Well, you are right, as well as the code. It is the explanation that gives those inaccuracies. I have updated the post now. Thanks!


  • 0
    R

    Thanks! get it! BTW, can you tell me how to make the font of the numbers display like yours?It's so clear!


  • 0

    Hi, rlaoyao. You mean numbers, right? Well, simply quote your words with `


  • 0
    R

    Great,Thanks!


Log in to reply
 

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