## Monday, November 24, 2014

### [LeetCode] Best Time to Buy and Sell Stock I, II, II

Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

I限制了只能买卖一次。于是要尽可能在最低点买入最高点抛出。这里的一个隐含的限制是抛出的时间必须在买入的时间之后。所以找整个数组的最大最小值之差的方法未必有效，因为很可能最大值出现在最小值之前。但是可以利用类似思路，在扫描数组的同时来更新一个当前最小值minPrice。这样能保证当扫到i时，minPrices必然是i之前的最小值。当扫到i时：

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14``` ```class Solution { public: int maxProfit(vector &prices) { if(prices.empty()) return 0; int ret = 0, minPrice = prices[0]; for(int i=1; i

II并没有限制总的买卖次数，只限制了当天只能买或卖。所以可以采用greedy的方法，来获得所有可能的正利润。以如下序列说明：

2 1 3 4 5 4 2 8 7

 ``` 1 2 3 4 5 6 7 8 9 10``` ```class Solution { public: int maxProfit(vector &prices) { int ret = 0; for(int i=1; iprices[i-1] ? prices[i]-prices[i-1] : 0; } return ret; } }; ```

III是这三题中最难的。允许两次买卖，但同一时间只允许持有一支股票。也就意味着这两次买卖在时间跨度上不能有重叠（当然第一次的卖出时间和第二次的买入时间可以是同一天）。既然不能有重叠可以将整个序列以任意坐标i为分割点，分割成两部分：

prices[0:n-1] => prices[0:i] + prices[i:n-1]

1. 计算A[0:i]的收益最大值：用minPrice记录i左边的最低价格，用maxLeftProfit记录左侧最大收益
2. 计算A[i:n-1]的收益最大值：用maxPrices记录i右边的最高价格，用maxRightProfit记录右侧最大收益。
3. 最后这两个收益之和便是以i为分割的最大收益。将序列从左向右扫一遍可以获取1，从右向左扫一遍可以获取2。相加后取最大值即为答案。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29``` ```class Solution { public: int maxProfit(vector &prices) { if(prices.empty()) return 0; int n = prices.size(); vector leftProfit(n,0); int maxLeftProfit = 0, minPrice = prices[0]; for(int i=1; i=0; i--) { if(prices[i]>maxPrice) maxPrice = prices[i]; else maxRightProfit = max(maxRightProfit, maxPrice-prices[i]); ret = max(ret, maxRightProfit + leftProfit[i]); } return ret; } }; ```