【风口之下，猪都能飞】（一道算法面试题） （待续）

题目：

风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2 <= n <= 100, 0 <= prices[i] <= 100

输入例子:

3, 8, 5, 1, 7, 8

解析：

这道题需要注意的地方在于，“买入前一定要保证手上没有股票”。

因此我们可以假设在数组的第一天买入（第一次买入），

第二天卖出（第一次卖出）

同时第二天买入（第二次买入）

第三天卖出（第二次卖出）

如下图：

可以通过4个for循环不断令这4个日期偏移，得出所有可能的买卖天数及对应的收益，并取最大值并返回它。

用代码实现如下：

int calculateMax(vector<int> &prices)
{
	int sz = prices.size();
	int remain_value1 = 0;
	int remain_value2 = 0;
	int ret = 0;

	if (sz == 2)
	{
		if (prices[1] - prices[0] > 0)
		{
			return prices[1] - prices[0];
		}
		else
		{
			return 0;
		}
	}
	int buy1_pos = 0;
	int sell1_pos = 1;
	int buy2_pos = sell1_pos;
	int sell2_pos = buy2_pos + 1;

	int buy1_prices = prices[buy1_pos];
	int buy2_prices = prices[buy2_pos];
	int sell1_prices = prices[sell1_pos];
	int sell2_prices = prices[sell2_pos];


	for (buy1_pos = 0; buy1_pos < sz - 1; buy1_pos++)
	{
		buy1_prices = prices[buy1_pos];
		for (sell1_pos = buy1_pos + 1; sell1_pos < sz; sell1_pos++)
		{
			sell1_prices = prices[sell1_pos];
			for (buy2_pos = sell1_pos; buy2_pos < sz - 1; buy2_pos++)
			{
				buy2_prices = prices[buy2_pos];
				for (sell2_pos = buy2_pos + 1; sell2_pos < sz; sell2_pos++)
				{
					sell2_prices = prices[sell2_pos];
					if (remain_value1 < sell1_prices - buy1_prices)
					{
						remain_value1 = sell1_prices - buy1_prices;
					}
					if (remain_value2 < sell2_prices - buy2_prices)
					{
						remain_value2 = sell2_prices - buy2_prices;
					}
					if (ret < remain_value1 + remain_value2)
					{
						ret = remain_value1 + remain_value2;
					}
				}
				remain_value1 = 0;
				remain_value2 = 0;
			}
		}
	}
	return ret;
}

这种方法简单粗暴，思路简单，但效率并不高，可以看出时间复杂度是O(N^4).

【风口之下，猪都能飞】（一道算法面试题） （待续）

原文：http://zhweizhi.blog.51cto.com/10800691/1762813