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 besell + 1 to check for the remaining prices.
The code is as follows.
1 class Solution { 2 public: 3 int maxProfit(vector<int>& 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 };
This post shares a super-concise code, which is rewritten below.
1 class Solution { 2 public: 3 int maxProfit(vector<int> &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.