1.題目描述

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 (ie, you must sell the stock before you buy again).

2.解法分析

限定了交易次數之后題目就需要我們略微思考一下了，由于有兩次交易的機會，那么我們選定一個時間點t_i，將此時間點作為兩次交易的支點的話，必然有：

????? t₀….t_i之內滿足最佳交易原則，t_i-t_n天也滿足最佳交易原則，那么這就是一個動態規劃的策略了，于是有下面的代碼：

?

class Solution { public: int maxProfit(vector<int> &prices) { // Start typing your C/C++ solution below // DO NOT write int main() function if(prices.size() <=1)return 0; vector<int>::iterator iter; ? for(iter=prices.begin();iter!=prices.end()-1;++iter) { *iter = *(iter+1) - *iter; } prices.pop_back(); vector<int>accum_forward; vector<int>accum_backward; int max = 0; int subMax = 0; for(iter=prices.begin();iter!=prices.end();++iter) { subMax += *iter; if(subMax > max)max=subMax; else if(subMax<0)subMax = 0; accum_forward.push_back(max); } vector<int>::reverse_iterator riter; max =0 ; subMax = 0; for(riter=prices.rbegin();riter!=prices.rend();++riter) { subMax +=*riter; if(subMax >max)max = subMax; else if(subMax<0)subMax=0; accum_backward.push_back(max); } max =0; int len = accum_forward.size(); for(int i=0;i<len-1;++i) { if((accum_forward[i]+accum_backward[len-i-2])>max) max = accum_forward[i]+accum_backward[len-i-2]; } return max>accum_forward[len-1]?max:accum_forward[len-1]; } };

?

ps:做完題之后提交，發現老是AC不了，有個case總是解決不了，本來以為是自己代碼寫得有問題，檢查了半天沒發現錯誤，于是開始看別人怎么寫，結果發現別人AC的代碼也過不了，猜想可能系統還是做得不完善，應該是后臺的線程相互干擾了，過了一段時間果然同樣的代碼又可以AC了。在這段過程中，看別人寫的代碼，發現了一個比我簡潔一些的寫法，雖然我么你的復雜度是一樣的，但是此君代碼量比我的小一點，以后學習學習，另外，一直不知道vector還可以預先分配大小，從這個代碼里面也看到了，算是有所收獲。附代碼如下：

class Solution { public: int maxProfit(vector<int> &prices) { // null check int len = prices.size(); if (len==0) return 0; ? vector<int> historyProfit; vector<int> futureProfit; historyProfit.assign(len,0); futureProfit.assign(len,0); int valley = prices[0]; int peak = prices[len-1]; int maxProfit = 0; ? // forward, calculate max profit until this time for (int i = 0; i<len; ++i) { valley = min(valley,prices[i]); if(i>0) { historyProfit[i]=max(historyProfit[i-1],prices[i]-valley); } } ? // backward, calculate max profit from now, and the sum with history for (int i = len-1; i>=0; --i) { peak = max(peak, prices[i]); if (i<len-1) { futureProfit[i]=max(futureProfit[i+1],peak-prices[i]); } maxProfit = max(maxProfit,historyProfit[i]+futureProfit[i]); } return maxProfit; } };

轉載于:https://www.cnblogs.com/obama/p/3250251.html

總結

以上是生活随笔為你收集整理的leetcode—Best Time to Buy and Sell stocks III的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。