8ms Easy C++ Solution

• 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 (sell + 1 < n && prices[sell + 1] > prices[sell])
sell++;
}
return profit;
}
};
``````

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

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

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

• This post is deleted!

• 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.

• 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!

• 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!

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

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

• `Great,`Thanks!

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