problem:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
题目的意思已知每天股票的价格，最多进行两次交易(买卖操作），能够赚取的最大利润。（每天最多只能进行一次操作：买或卖；且必须卖出手头持有股票后，才能进行下一次购买）
思路很简单，我们可以把区间划分为两部分，分别求两部分的最大利润值，然后叠加。比较所有划分，求得最大值。
当然，由于我们也可以只进行一次交易，所以还需要考虑不划分时的最大利润值。
基于以上思路，可以很快写出如下O(n^2) 复杂度的算法：
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int profit = max(0, getMax(prices, 0, n)); for(int i = 2; i < n - 1;i++) { profit = max(profit, getMax(prices, 0, i) + getMax(prices, i, n)); } return profit; } int getMax(vector<int>& prices, int i, int j) { int maxnum = INT_MIN; int minnum = INT_MAX; for(int k = i; k < j; k++) { if(minnum != INT_MAX) maxnum = max(maxnum, prices[k] - minnum); minnum = min(minnum, prices[k]); } return maxnum; } };
看起来很清晰，但会超时。原因在于getMax函数存在大量重复计算。比如，在计算左区间( 0, i ) 时，我们可以从( 0, i - 1) 的结果推出, 只需要判断新加入的价格是否高于之前的最高价格，也就是：
dp[ i ] = dp[ i - 1 ] （ price[ i ] <= prevMaxNum ) // dp[ i - 1 ] = prevMaxNum - prevMinNum
dp[ i ] = price[ i ] - prevMinNum （ price[ i ] > prevMaxNum )
优化后，得到O(N)的算法：
class Solution { public: int n; vector<int> leftMax; vector<int> rightMax; void calLeftMax(vector<int>& prices) { int res = INT_MIN; int minnum = INT_MAX; for(int k = 0; k < n; k++) { if(minnum != INT_MAX) { res = max(res, prices[k] - minnum); if(res > 0) { leftMax[k] = res; } } minnum = min(minnum, prices[k]); } } void calRightMax(vector<int>& prices) { int maxnum = INT_MIN; int res = INT_MIN; for(int k = n - 1; k >= 0; k--) { if(maxnum != INT_MIN) { res = max(res, maxnum - prices[k]); if(res > 0) { rightMax[k] = res; } } maxnum = max(maxnum, prices[k]); } } int maxProfit(vector<int>& prices) { n = prices.size(); if(n == 0) return 0; leftMax.resize(n, -1); rightMax.resize(n, -1); calLeftMax(prices); calRightMax(prices); int profit = max(0, leftMax[n - 1]); for(int i = 2; i < n - 1;i++) { profit = max(profit, leftMax[i] + rightMax[i]); // cout <<leftMax[i] << " " << leftMax[i] << endl; } return profit; } };
[动态规划] leetcode 123 Best Time to Buy and Sell Stock III
原文：https://www.cnblogs.com/fish1996/p/11261611.html