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).
這次是可以進行兩次股票交易，
我們知道，單次最大獲利可以通過DP獲得，我們利用minV記錄出現的交易最低價格，即可得DP方程dp[i]=max(a[i]-minV,dp[i-1])
此方程的含義是最優解來自于：賣出目前股票 or 在之前賣出股票擷取的最大值 于是可以得到i位置的最大獲利。
但是顯然還不夠，我們需要找出兩支股票交易獲利最大值。
那麼如果做過九度的合唱隊形這道題就可能發現，可以從後往前找獲利的最大值。
兩個獲利最大值相加，即為兩支股票獲利的最大值。
即我們需要找出兩個最大差距的兩個點對。
不過有人可能提出疑問，既然都是在i點那不就是從i點賣出又買入了？
那下圖的情形如何解釋呢？
仔細想想，其實我們的i點并不一定代表将股票賣出，而是從邊界點開始往這一點所獲利的最大值。
也就是說f[i]+g[i]雖然同為i，但是它們表示的意思是在i點能取得的最大利潤，而非合唱隊形那樣以i再次為出發點找最長不下降序列。
int maxProfit(vector<int>& prices) {
if(prices.size()<2) return 0;
int n=prices.size();
vector<int> f(n,0);
vector<int> g(n,0);
int small=prices[0];
for(int i=1;i<n;i++){
small=min(prices[i],small);
f[i]=max(f[i-1],prices[i]-small);
}
int big=prices[n-1];
for(int i=n-2;i>=0;i--){
big=max(prices[i],big);
g[i]=max(g[i+1],big-prices[i]);
}
int maxV=0;
for(int i=0;i<n;i++) {
if(f[i]+g[i]>maxV)
maxV=f[i]+g[i];
}
return maxV;
}
PLUS:網上有說将其轉化為差分數組再求最大m段和的情況【m=2】。
例如對于例子：1,4,6,3,7
形成差分數組[0,3,2,-3,4]，于是最大2段和為3+2 + 4=9;
能夠使用最大兩段和的原因在于，對于同一天如果賣出和買入同時發生，那麼可以當做這一天沒有交易。
也就是說，，上例的最終結果應當是(6-1)+(7-3)=9；
但是，同樣可以寫成(6-4 + 4-1) + (7-3) = 9
對應到差分數組裡，就是兩項的和。
對于這幾個股票題的差分數組解法，可以參考：http://www.cnblogs.com/apoptoxin/p/3770092.html
對于差分數組的了解，可以參考：https://www.zybuluo.com/rapiz/note/360515
嗯，這樣就成功地轉化了問題，然後最大m段和怎麼求呢？
沒有看過最大m子段和問題的同學可以看一下我的另一篇部落格：http://blog.csdn.net/u013033845/article/details/52278766
但是~！！！
要注意狀态轉移有個很重要的差別在于...【這個bug修了一個多小時orz】
最大m段和要求不重疊，但是這個問題裡面m段和是可以重疊的！
什麼意思呢，舉個例子：
2,1,4，差分數組為0,-1,3
如果按照正常的矩陣推我們可以得到：
這個結果顯然是(1-2)+(4-1)=2所得到的，然而實際上有更優的政策是：
(2-2)+(1-4)=2 也就是說，在任何一天都可以當做買入賣出股票且沒有收益。在考慮第2子段的時候，可以不需要為第1子段留那一個位置的空間。
相應的，dp方程變為：
dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j]);(i=<k<j)
隻有這樣才可以得出正确的結果。
隻不過很遺憾，最大m子段和的複雜度是O(mn^2)【似乎可以優化來着】
這篇部落格對這個算法進行了深入探讨：http://blog.csdn.net/liufeng_king/article/details/8632430
于是利用這個樸素思路寫出來的交到oj上逾時了。
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n<2) return 0;
for(int i=n-1;i>0;i--)
prices[i]=prices[i]-prices[i-1];
prices[0]=0;
int dp[3][n],final=0;
memset(dp,0,sizeof(dp));
//最大m子段和
for(int i=1;i<=2;i++){
dp[i][i-1]=prices[i-1];
for(int j=i;j<n-2+i;j++){
int maxV=dp[i-1][i-2];
for(int k=i-2;k<j;k++){
if(dp[i-1][k]>maxV)
maxV=dp[i-1][k];
}
dp[i][j]=max(dp[i][j-1],maxV)+prices[j];
final=max(final,dp[i][j]);
}
final=max(final,dp[i][i-1]);
}
return final;
}
于是利用了改進的方法，Accepted!!!!
改進的地方主要在于，由于每次使用到的是i行的最大值和i-1行的最大值。
故使用兩個數組将其存起來，每次使用b[i]=b[i-1]+a[i] or c[i-1]+a[i]
可以确定，第i行每次進行運算之後的将是這一行目前的最大值，具體可參照下圖：
故每次周遊j的時候，需要将maxV更新到b[j]
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n<2) return 0;
//構造差分數組
for(int i=n-1;i>0;i--)
prices[i]=prices[i]-prices[i-1];
prices[0]=0;
prices.insert(prices.begin(),0);
int b[n],c[n];
memset(b,0,sizeof(b));//b數組記錄第i行的最大i子段和
memset(c,0,sizeof(c));//c數組記錄第i-1行的最大i-1子段和
for(int i=1;i<=2;i++) {
b[i]=b[i-1]+prices[i];
int maxV=b[i];
for(int j=i;j<=n-2+i;j++){
if(b[j-1]>c[j-1])
b[j]=b[j-1]+prices[j];
else b[j]=c[j-1]+prices[j];
c[j-1]=maxV;
if(b[j]>maxV)
maxV=b[j];
}
c[i+n-2]=maxV;
}
int sum = 0;
for(int j=0; j<=n; j++){
if(sum<b[j]){
sum = b[j];
}
}
return sum;
}