Leetcode Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which theithelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete at mosttwotransactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

要掌握这种思想：

1 两段分段思想
2 前往后，后往前都可以处理数列的思想

时间复杂度是O(n)，不掌握这种思想是很难做出来的。

class Solution {
public:
    int maxProfit(vector<int> &prices) 
	{
		vector<int> profit(prices.size()+1);

		int buy = INT_MAX;
		for (int i = 0; i < prices.size(); i++)
		{
			if (prices[i] < buy) buy = prices[i];
			else profit[i+1] = max(profit[i], prices[i]-buy);
		}

		int sale = INT_MIN , max_profit = 0, res = 0;
		for (int i = prices.size() - 1; i >= 0 ; i--)
		{
			if (prices[i] > sale) sale = prices[i];
			else max_profit = max(max_profit, sale - prices[i]);
			profit[i+1] = profit[i+1]+ max_profit;
			res = max(profit[i+1], res);
		}
		return res;
	}
};

更新：

原始程序：

//2014-2-17 update
	int maxProfit(vector<int> &prices) 
	{
		if (prices.size() < 2) return 0;

		int *ta1 = new int[prices.size()+1];
		ta1[0] = 0;
		int lowest_point = INT_MAX;

		for (int i = 0; i < prices.size(); i++)
		{
			if (prices[i] < lowest_point) lowest_point = prices[i];
			ta1[i+1] = max(prices[i]-lowest_point, ta1[i]);
		}

		int *ta2 = new int[prices.size()+1];
		ta2[prices.size()] = 0;
		int h_point = INT_MIN;

		for (int i = prices.size() - 1; i >= 0 ; i--)
		{
			if (prices[i] > h_point) h_point = prices[i];
			ta2[i] = max(ta2[i+1], h_point-prices[i]);
		}

		int max_profit = 0;
		for (int i = 0; i < prices.size(); i++)
		{
			max_profit = max(max_profit, ta1[i]+ta2[i]);
		}

		delete []ta1;
		delete []ta2;
		return max_profit;
	}

简化程序：

//2014-2-17 update
	int maxProfit(vector<int> &prices) 
	{
		int *ta1 = new int[prices.size()+1];
		ta1[0] = 0;
		int point = INT_MAX;

		for (int i = 0; i < prices.size(); i++)
		{
			if (prices[i] < point) point = prices[i];
			ta1[i+1] = max(prices[i]-point, ta1[i]);
		}
		point = INT_MIN;
		for (int i = prices.size() - 1; i >= 0 ; i--)
		{
			if (prices[i] > point) point = prices[i];
			ta1[i] = max(ta1[i+1], point-prices[i]+ta1[i]);
		}
		return ta1[0];
	}