This problem is similar to . 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 besell + 1
to check for the remaining prices
.
The code is as follows.
1 class Solution { 2 public: 3 int maxProfit(vector & prices) { 4 int buy = 0, sell = 0, profit = 0, n = prices.size(); 5 while (buy < n && sell < n) { 6 while (buy + 1 < n && prices[buy + 1] < prices[buy]) 7 buy++; 8 sell = buy; 9 while (sell + 1 < n && prices[sell + 1] > prices[sell])10 sell++;11 profit += prices[sell] - prices[buy];12 buy = sell + 1;13 }14 return profit;15 }16 };
shares a super-concise code, which is rewritten below.
1 class Solution {2 public:3 int maxProfit(vector &prices) {4 int res = 0;5 for (int p = 1; p < (int)prices.size(); ++p) 6 res += max(prices[p] - prices[p - 1], 0); 7 return res;8 }9 };
The above code cleverly takes advantage of the cancelling of neighboring elements in prices to give the correct result.