博文中会简要介绍Leetcode P0122题目分析及解题思路。
“Best Time to Buy and Sell Stock III”这道题是一道比较难的题目，其原型题是p0188。原型题中要求计算最多买卖k次所能获得的最大收益，这里其实就是令k=2而已。这篇博文会直接解决其原型题，给出基于动态规划的通用思路。
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 (i.e., you must sell the stock before you buy again).
这道题的动态规划思路比较难一点，但是也同样属于套路题。如果还记得p0115这道题的思路的话，不难发现这类套路的共同点。
在p0115中我们定义最优子结构的思路如下，
dp[i][j]表示s[0:i-1]区间（即s内前i个字符）内能够构成t[0:j-1]（即t内前j个字符）的不同子序列最大总数。
而这道题同样类似，我们可以类比的得到最优子结构，如下，
dp[i][j]表示前i天里最多交易j次的最大收益
如此一来，当我们得到dp[n][k]时，就能得到在这个n天的区间内能够得到的最大收益。得到最优子结构后，我们就能够比较容易地得到递推表达式，如下，
令dp[i][j]表示前i天里最多交易j次的最大收益
dp[0][0] = 0
dp[i][0] = 0
dp[0][i] = 0
显然无论是那种情况，如果允许的交易次数为零或者股票预测区间的长度为零，都会导致实际的收益为零，
dp[i][j] = max(dp[i][j-1], prices[j]-prices[m]+dp[m][j-1]), 1 <= m <= i-1
这里其实表示，前i天如果最多交易j次的话，最大收益只有两种可能，一种是不交易第j次，那么此时收益就相当于在前i天里交易j-1次；第二种是在交易第j次，并且是第m天买入，第i天卖出，那么此时收益就等于第i天股价和第m天股价的差值再加上前m天内的最大收益。
这里有个小优化。如果我们按照上述递推表达式来做，那么动态规划维度是三维的，也就是说时间复杂度会上升到O(n^3)。但是如果我们观察此式，会发现，
max(dp[i][j-1], prices[j]-prices[m]+dp[m][j-1]) = max(dp[i][j-1], prices[j]+max(dp[m][j-1]-prices[m]))
也就是说，我们如果知道了下式的值，
max(dp[m][j-1]-prices[m]))
就可以直接参与计算。而这个式子的值在遍历到第m天的时候就可以计算出来，也就是说我们对i进行遍历的时候，不需要每次再用m从1遍历到i-1，而是可以通过维护一个变量去记录第m天的该式的值即可
除了使用原型题的动态规划通用解法来解决这道题以外，也可以针对这道题设计特例解法。特例解法的详解写在了C++注释中，可以参考C++代码实现
以下是Java的题解代码实现。
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1)
return 0;
int days = prices.length, k = 2;
int[][] dp = new int[days+1][k+1];
// DP
for (int j2=1; j2<=k; ++j2) {
int localMax = dp[0][j2-1]-prices[0];
for (int i1=1; i1<=days; ++i1) {
dp[i1][j2] = Math.max(dp[i1-1][j2], prices[i1-1]+localMax);
localMax = Math.max(localMax, dp[i1][j2-1]-prices[i1-1]);
}
}
return dp[days][k];
}
}
以下是C++的题解代码实现。
/**
允许两次买卖，但同一时间只允许持有一支股票。也就意味着这两次买卖在时间跨度上不能有重叠（当然第一次的卖出时间和第二次的买入时间可以是同一天）。既然不能有重叠可以将整个序列以任意坐标i为分割点，分割成两部分：
prices[0:n-1] => prices[0:i] + prices[i:n-1]
对于这个特定分割来说，最大收益为两段的最大收益之和。每一段的最大收益当然可以用I的解法来做。而III的解一定是对所有0<=i<=n-1的分割的最大收益中取一个最大值。为了增加计算效率，考虑采用dp来做memorization。目标是对每个坐标i：
1. 计算A[0:i]的收益最大值：用minPrice记录i左边的最低价格，用maxLeftProfit记录左侧最大收益
2. 计算A[i:n-1]的收益最大值：用maxPrices记录i右边的最高价格，用maxRightProfit记录右侧最大收益。
3. 最后这两个收益之和便是以i为分割的最大收益。将序列从左向右扫一遍可以获取1，从右向左扫一遍可以获取2。相加后取最大值即为答案。
*/
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1)
return 0;
int days = prices.size(), left_min = prices[0], left_max_profit = 0;
int *left_profit = new int[days];
for (int i1=1; i1<days; ++i1) {
if (prices[i1] < left_min)
left_min = prices[i1];
else
left_max_profit = max(prices[i1]-left_min, left_max_profit);
left_profit[i1] = left_max_profit;
}
int max_profit = left_profit[days-1], right_max = prices[days-1], right_max_profit = 0;
for (int i1=days-2; i1>=0; --i1) {
if (prices[i1] > right_max)
right_max = prices[i1];
else
right_max_profit = max(right_max-prices[i1], right_max_profit);
max_profit = max(max_profit, left_profit[i1]+right_max_profit);
}
return max_profit;
}
};