[LeetCode]Best Time to Buy and Sell Stock III

结合Best Time to Buy and Sell Stock 和 Max Subarray II的解法，左右扫一遍就行，从左到右的DP方程Best Time to Buy and Sell Stock是一样的，从右到左就按照 Max Subarray II的方法反过来就行了，注意这里我们同一天先卖了在买是允许的，只要同一时间手上不超过两个股票就行。时间复杂度课空间复杂度都是O(n)，代码如下：

	class Solution {
	public:
	int maxProfit(vector<int>& prices) {
	if(prices.size() < 2)return 0;
	int len = prices.size(), minPrice = prices[0], res = 0;
	vector<int> dp(len, 0);
	for(int i = 0; i < len; ++i)
	{
	minPrice = min(minPrice, prices[i]);
	dp[i] = max(dp[i - 1], prices[i] - minPrice);
	}
	int maxPrice = INT_MIN, currMaxProfit = 0;
	for(int i = len - 1; i >= 0; --i)
	{
	maxPrice = max(maxPrice, prices[i]);
	currMaxProfit = max(currMaxProfit, maxPrice - prices[i]);
	res = max(res, dp[i] + currMaxProfit);
	}
	return res;
	}
	};

view raw Best Time to Buy and Sell Stock III.cpp hosted with ❤ by GitHub