//from codeganker.
使用动态规划来完成，事实上可以解决非常通用的情况，也就是最多进行k次交易的情况。
这里我们先解释最多可以进行k次交易的算法，然后最多进行两次我们只需要把k取成2即可。我们还是使用“局部最优和全局最优解法”。
我们维护两种量，一个 是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易 在当天卖出的最好的利润是多少（local[i][j]）。下面我们来看递推式，全局的比较简单，如果第i天有卖出，那么global[i][j]=local[i][j]；如果第i天没有卖出，那么global[i][j]=global[i-1][j]。
综合以上两种情况，global[i][j]=max(local[i][j],global[i-1][j]). （*）
local[i][j]的划分标准是根据它的最后一次交易的买入时间t。（ diff = prices[i] - prices[i - 1]. ）
1)如果t<i-1,那么local[i][j]= local[i-1][j]+diff（这种情况有些难想到，但可以通过cut-and-paste 反证法来证明。在这种情况下，把 local[i-1][j]的最后一次交易的卖出时间从第i-1天延迟到第i天，就得到了local[i][j]的最后一次交易的 c。）
2)如果t=i-1，那么local[i][j]=global[i-1][j-1]+diff
3)如果t=i, 那么local[i][j]=global[i-1][j-1]+0
综合以上三种情况，local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)
/*
第三种情况似也可不用考虑。因为如果不断删除这种当天进行了一次先买入后卖出的无意义操作，
a）最后还剩下唯一一个卖出操作，则它必定等价于1)或2）中的一种情况。
b）最后没有操作剩下，则相当于当天没有任何操作。但是，这种情况不会影响global[i][j]的值（global[i][j]取global[i-1][j]就可以了）。而最后我们是根据global的值来得出最大利润的。所以，情形3）不考虑时，可能影响local[i][j]的值，但不会影响最后我们要的结果。情形3）不考虑时，相当于禁止出现当天进行先买入后卖出的无意义操作。此时，回到开头我们对local[i][j]的定义可以更严格一些：
local[i][j]：当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出，并且这种交易不是先买入后卖出的无意义情况的，最好的利润。
(其实也可以从题目一开始就声明不允许存在这样的交易，因为这样的交易没有任何意义，白白浪费了一次交易机会。这样对local的定义，就不需要特别说明了。)
*/
上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)，如果是最多进行两次交易，那么复杂度还是O(n)。空间上只需要维护当天数据就可以，所以是O(k)，当k=2，则是O(1)。代码如下：
int maxProfit(vector<int> &prices) {
if(prices.size()==0)
return 0;
int local[3]={0};
int global[3]={0};
for(int i=1;i<prices.size();i++){
int diff=prices[i]-prices[i-1];
for(int j=2;j>=1;j--){
local[j]=max(local[j]+diff,global[j-1]+max(diff,0));
global[j]=max(local[j],global[j]);
}
}
return global[2];
}
楼主你背后的得到这个思路的思维过程是怎样的能分享一下吗？
其实也没什么通法，就是试试看哈~
Bin Mu2014年10月25日 上午6:34
代码中的for循环，为什么j是从2到1，而不是从1到2呢？j是交易次数，按道理应该从小到大来求啊。
删除
对，这个是动态规划要省空间常用的技巧哈~ 就是看数据是要旧的还是新的，这里是要旧的，所以要从大到小~
扩展：下面的代码同时打印出最大利润时的交易操作。现在有一个缺点是只能打印一种可能。如下例子就有两种操作序列都能实现最大利润：
Input: k = 2, prices = [4, 4, 6, 1, 1, 4, 2 ,5]
max profit: 6
Explanation: 1)Buy at 4 and sell at 6. Then buy at 1 and sell at 5. Your profit is 2 + 4 = 6.2)Buy at 1 and sell at 4. Then buy at 2 and sell at 5. Your profit is 3 + 3 = 6.
思路： prelocal[i][j] 保存了local[i][j]的最后一次交易的买入时间（最后一次交易的卖出时间，
根据local的定义即为i）
根据local的定义即为i）
经过一番努力，现在的代码可以打印全部可能的操作序列了：
#include <iostream>
#include <vector>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace::std;
void printActions( vector<vector<int> >&global,int p,int q, vector<vector<int> >&local, vector<vector<set<int> > >&prelocal,vector<int>&actions,vector<vector<int> >&collect);
/*综合以上两种情况，global[i][j]=max(local[i][j],global[i-1][j]).
local[i][j]的划分标准是根据它的最后一次交易的买入时间t。
如果t<i-1,那么local[i][j]= local[i-1][j]+diff
如果t=i-1，那么local[i][j]=global[i-1][j-1]+diff
如果t=i, 那么local[i][j]=global[i-1][j-1]+0
综合以上三种情况，local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)*/
int maxProfit(vector<int> &prices,int k) {
int n =prices.size();
if(prices.size()==0)
return 0;
//int local[3]={0};
//int global[3]={0};
vector<vector<int> > local(n,vector<int>(k+1,0));
vector<vector<set<int> > > prelocal(n,vector<set<int> >(k+1,set<int>()));
//for(int i=0;i<k+1;i++)
// prelocal[0][i].push_back(0);
vector<vector<int> > global(n,vector<int>(k+1,0));
for(int i=1;i<prices.size();i++){
int diff=prices[i]-prices[i-1];
for(int j=k;j>=1;j--){
local[i][j]=max(local[i-1][j]+diff,global[i-1][j-1]+max(diff,0));
if(local[i][j]==local[i-1][j]+diff)
prelocal[i][j]=prelocal[i-1][j];
if(local[i][j]==global[i-1][j-1]+diff)
prelocal[i][j].insert(i-1);
if(local[i][j]==global[i-1][j-1]+0)
prelocal[i][j].insert(i);
global[i][j]=max(local[i][j],global[i-1][j]);
}
}
/*debug info
for(int i=0;i<prelocal.size();i++){
for(int j=0;j<prelocal[i].size();j++){
cout<<i<<" "<<j<<": ";
for(set<int>::iterator it=prelocal[i][j].begin();it!=prelocal[i][j].end();it++)
cout<<*it<<" ";
cout<<endl;
}
}
*/
vector<int> actions;
vector<vector<int> > collect;
printActions(global,n-1,k,local,prelocal,actions,collect);
for(int i=0;i<collect.size();i++){
for(int j=0;j<collect[i].size();j++)
cout<<collect[i][collect[i].size()-1-j]<<" ";
cout<<endl;
}
return global[n-1][k];
}
void printActions( vector<vector<int> >&global,int p,int q, vector<vector<int> >&local, vector<vector<set<int> > >&prelocal,vector<int>&actions,vector<vector<int> >&collect){
if(global[p][q]==0) {
collect.push_back(actions);
return;}
if(global[p][q]==global[p-1][q])
printActions(global,p-1,q,local,prelocal,actions,collect);//should not use return here,
//because global[p][q]==local[p][q] may also be true;
if(global[p][q]==local[p][q]) {
for(set<int>::iterator it=prelocal[p][q].begin();it!=prelocal[p][q].end();it++){
actions.push_back(p+1);//when output, let day index start from 1
actions.push_back(*it+1);
//p=prelocal[p][q][i];
//q--;
printActions(global,*it,q-1,local,prelocal,actions,collect);
actions.pop_back();
actions.pop_back();
}
}
}
int main() {
std::cout << "Hello World!\n";
vector<int> vect{4, 4, 6, 1, 1, 4, 2 ,5};
int aa=maxProfit(vect,2);
cout<<"max: "<<aa<<endl;
/*
//test code
vector<int> vect2;
srand((unsigned)time(0));
for(int i=0;i<11;i++)
vect2.push_back(rand()%100);
vect2.push_back(vect2.back());
for(int i=0;i<vect2.size();i++)
cout<<vect2[i]<<" ";
cout<<endl;
cout<<"actions: "<<endl;
int aa=maxProfit(vect2,3);
cout<<"max: "<<aa<<endl; */
}
下面的代码删除了产生的没意义操作的情况（当天先买入后卖出），同时确保每天只能进行一个操作
操作（2）没有卖出操作，都能产生global的最大值。而当（2）也能获得最大值，说明（1）的卖出
操作，只是先买入后卖出的无意义情况。故当使用这种条件来排除这天，就漏掉了（2）的情况了。 { continue; } */ if(actions.size()>0&&p+1==actions.back()) continue; actions.push_back(p+1);//when output, let day index start from 1 actions.push_back(*it+1); printActions(global,*it,q-1,local,prelocal,actions,collect); actions.pop_back(); actions.pop_back(); } } }
