[LeetCode] Best Time to Buy and Sell Stock II

This problem is similar to the one Best time to sell and buy stock. To maximize the profit, in each time interval [a, b], we choose day i such that prices[i] is the local minimum ofprices[a..b] and day j such that prices[j] is the local maximum of prices[a..b]. Then the max profit in interval [a, b] is prices[j] - prices[i] if j > i or simply 0 otherwise.

Suppose we are given n days [1..n], we need to find the first local minimum (supposed to bebuy) and the first local maximum (called sell), then if buy < sell, the transaction is valid and we earn the profit, after which we update both buy and sell to be the starting point of the next interval sell + 1. Otherwise if buy > sell, we need to update sell to be at least buy + 1(updating sell to buy is meaningless since it will give profit of 0, which can be handled by initializing max_profit to be 0).

Well, now comes the following code, with comments.

 1     int maxProfit(vector<int>& prices) {
 2         int max_profit = 0, buy = 0, sell = 0;
 3         while (buy < prices.size() && sell < prices.size()) {
 4             if (buy < prices.size() - 1 && prices[buy] > prices[buy + 1]) buy++; // move buy to local minimum
 5             else if (sell < prices.size() - 1 && prices[sell] < prices[sell + 1]) sell++; // move sell to local maximum
 6             else 
 7                 if (buy < sell){ 
 8                     // the transaction is valid, take it and update buy and sell to be the starting point of the next interval
 9                     max_profit += prices[sell] - prices[buy];
10                     buy = ++sell;
11                 }
12                 else sell = buy + 1; // the date to sell need to be after the day to buy
13         }
14         return max_profit;
15     }

[LeetCode] Best Time to Buy and Sell Stock II

原文：http://www.cnblogs.com/jcliBlogger/p/4548108.html