[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).

思路：Best Time to Buy and Sell Stock I

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

如果prices[i] < minPrice，则更新minPrice = prices[i]。并且该天不应该卖出。

如果prices[i] >= minPrice，则该天可能是最好的卖出时间，计算prices[i] - minPrice，并与当前的单笔最大利润比较更新。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; int ret = 0, minPrice = prices[0]; for(int i=1; i<prices.size(); i++) { if(prices[i]<minPrice) minPrice = prices[i]; else ret = max(prices[i]-minPrice,ret); } return ret; } };

思路：Best Time to Buy and Sell Stock II

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

2 1 3 4 5 4 2 8 7

只要prices[i] - prices[i-1]>0，我们就在第i-1天买入，第i天抛出。这样可以包括所有可能赚取利润的区间。

1 2 3 4 5 6 7 8 9 10

class Solution { public: int maxProfit(vector<int> &prices) { int ret = 0; for(int i=1; i<prices.size(); i++) { ret += prices[i]>prices[i-1] ? prices[i]-prices[i-1] : 0; } return ret; } };

思路：Best Time to Buy and Sell Stock III

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

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

对于这个特定分割来说，最大收益为两段的最大收益之和。每一段的最大收益当然可以用I的解法来做。而III的解一定是对所有0<=i<=n-1的分割的最大收益中取一个最大值。为了增加计算效率，考虑采用dp来做bookkeeping。目标是对每个坐标i：

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<int> &prices) { if(prices.empty()) return 0; int n = prices.size(); vector<int> leftProfit(n,0); int maxLeftProfit = 0, minPrice = prices[0]; for(int i=1; i<n; i++) { if(prices[i]<minPrice) minPrice = prices[i]; else maxLeftProfit = max(maxLeftProfit, prices[i]-minPrice); leftProfit[i] = maxLeftProfit; } int ret = leftProfit[n-1]; int maxRightProfit = 0, maxPrice = prices[n-1]; for(int i=n-2; 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; } };