123 Best Time to Buy and Sell Stock III

题目

123 Best Time to Buy and Sell Stock III

题解

题目要求：给定N天的股票价格，至多进行两次交易，求能够得到的最大利润是多少。约束条件是不能同时进行多个交易，也就是各个交易的时间区间不能重叠，即买入之后必须卖出才能再次买入。

为了扩展算法的适用范围，这里把问题泛化为N天至多进行K次交易的问题。

以从简单到复杂的方式进行分析，若

1. 只有一天的价格，那么显然最大利润为0
2. 只有两天的价格，此时可以选择在第二天完成一次交易或不进行交易。如果选择在第二天通过卖出完成一次交易，那么就必须在第二天之前也就是第一天进行买入；如果不进行交易则会有第一天的最大利润。最大的利润就是两种情况中的最大值
3. 有三天的价格，此时可以根据前两天的最大利润进行判断，如果第三天没有进行交易，此时的利润与前两天的最大利润相同；若第三天进行了交易，那么则需要在前两天中选一天进行买入，并找出使利润最大化的买入日期，而要在这种情况下最大化利润，必须要使得买入日期前的最大利润加上此次交易的利润为最大值。
4. 给定一个具体的例子[1,4,2,7,6,8]，如果要求至第五天的最大利润，那么同样需要考虑是否在第五天完成一次交易。记\(subProblem[k][n]\)为n天前至多进行k次交易得到的最大利润，若在第五天不进行交易，那么就会有\(subProblem[k][n-1]\)这么多的利润；若在第五天完成一次交易，就需要选择一个日期\(j(j < 5)\)，使得\(subProblem[k-1][j-1] + (prices[5] - prices[j])\)最大化。两种结果中的最大值即为\(subProblem[k][5]\)（PS：在第五天买入只会亏不会赚，因为此时只考虑到第五天）

经过上述分析，可以看出这个问题能够用动态规划的策略解决。在0到第i天的时间段里，根据在第i天是卖出还是什么都不做，有状态转移方程 \(\begin{aligned} subProblem[k][i] = max( \\ subProblem[k][i-1], \\ max_{j}(prices[i] - prices[j] + subProblem[t-1][j-1]) \\ ) \\ where ~ j < i \end{aligned}\)

若从i=0计算到i=n，仔细观察后可以发现，对于\(max_{j}(prices[i] - prices[j] + subProblem[t-1][j-1]), where ~ j < i\)，其相当于

\[\begin{aligned} max (prices[i] + f[t-1, 0] - prices[0], \\ prices[i] + f[t-1, 1] - prices[1], \\ prices[i] + f[t-1, 2] - prices[2], \\ ... \\ prices[i] + f[t-1, i-1] - prices[i-1]) \end{aligned}\]

其中\(f[t-1, j] - prices[j]\)是包含了前一步即\(max_{j}(prices[i-1] - prices[j] + subProblem[t-1][j-1]) (j < i-2)\)计算过的部分的，因此只要在转移过程中不断进行max计算维护单个变量就可以了

代码

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

		int k = 2;
		vector<vector<int>> sub_problem(k + 1, vector<int>(size));

		int result = 0;
		result = dynamic_programming(prices, k, sub_problem);
		return result;
	}

private:
	int dynamic_programming(vector<int>& prices, int k, vector<vector<int>>& sub_problem) {
		int size = prices.size();
		if (k == 0 || size == 0)
		{
			return 0;
		}

		for (int transact = 1; transact <= k; transact++)
		{
			int last_buy_for_max_profit = sub_problem[transact - 1][0] - prices[0];
			for (int day = 1; day < size; day++)
			{
				int no_sell = sub_problem[transact][day - 1];
				int sell = prices[day] + last_buy_for_max_profit;
				last_buy_for_max_profit = max(last_buy_for_max_profit, sub_problem[transact - 1][day] - prices[day]);
				sub_problem[transact][day] = max(no_sell, sell);
			}
		}

		return sub_problem[k][size - 1];
	}
};