本文主要是介绍leetcode-123 Best Time to Buy and Sell Stock III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
此题是限制在两次交易内，相对要难一些。容易想到的解决办法是，把prices[] 分成两部分prices[0...m] 和 prices[m...length] ，分别计算在这两部分内做交易的做大收益。由于要做n次划分，每次划分可以采用 第一题： Sell Stock I的解法， 总的时间复杂度为O(n^2).
<span style="font-size:14px;">public class Solution {public int maxProfit(int[] prices) {int ans = 0;for(int m = 0; m<prices.length; m++){int tmp = maxProfitOnce(prices, 0, m) + maxProfitOnce(prices, m, prices.length-1);if(tmp > ans) ans = tmp;}return ans;}public int maxProfitOnce(int[] prices,int start, int end){if(start >= end) return 0;int low = prices[start];int ans = 0;for(int i=start+1; i<=end; i++){if(prices[i] < low) low = prices[start];else if(prices[i] - low > ans) ans = prices[i] - low;}return ans;}}</span>但是由于效率过低，运行超时。可以利用动态规划的思想进行改进，保持计算的中间结果，减少重复的计算。
那就是第一步扫描，先计算出子序列[0,...,i]中的最大利润，用一个数组保存下来，那么时间是O(n)。计算方法也是利用第一个问题的计算方法。 第二步是逆向扫描，计算子序列[i,...,n-1]上的最大利润，这一步同时就能结合上一步的结果计算最终的最大利润了，这一步也是O(n)。 所以最后算法的复杂度就是O(n)的。
就是说，通过预处理，把上面的maxProfitOnce()函数的复杂度降到O(1)
<span style="font-size:14px;">class Solution {public:int maxProfit(vector<int>& prices) {int len = prices.size();if(len == 0) return 0;vector<int> c(len,0);int tmpMax = 0;int min = prices[0];for(int i = 1; i < len; i++){ //正向遍历，tmpProfit[i]表示 prices[0...i]内做一次交易的最大收益.if(prices[i] < min) min = prices[i];else if(tmpMax < prices[i] - min) tmpMax = prices[i] - min;tmpProfit[i] = tmpMax;}vector<int> tmpProfitReverse(len,0);int max = prices[len - 1];tmpMax = 0;for(int j = len - 2; j >= 0; j--){ //逆向遍历, </span><span style="line-height: 27.2000007629395px; font-family: 'Helvetica Neue', Helvetica, Tahoma, Arial, STXihei, 'Microsoft YaHei', 微软雅黑, sans-serif; font-size: 14px;">tmpProfitReverse</span><span style="line-height: 27.2000007629395px; font-family: 'Helvetica Neue', Helvetica, Tahoma, Arial, STXihei, 'Microsoft YaHei', 微软雅黑, sans-serif;">[i]表示 prices[i...n-1]内做一次交易的最大收益</span><span style="font-size:14px;">
if(prices[j] > max ) max = prices[j];else if(tmpMax < max - prices[j]) tmpMax = max - prices[j];tmpProfitReverse[j] = tmpMax;}int res = 0;for(int k = 0; k < len; k++){tmpMax = tmpProfit[k] + tmpProfitReverse[k];if(tmpMax > res) res = tmpMax;}return res;}
};</span>这篇关于leetcode-123 Best Time to Buy and Sell Stock III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
