#include using namespace std; class Solution{ public: void maxProfit(vector prices){ int i,len=(int)prices.size(); int dp[len][2][3]; int last; //if array size is 1 we shud not //buy as no day to sell so //max profit is 0 if (len==1) { dp[0][0][0]=0; dp[0][0][1]=-1; dp[0][0][2]=-1; dp[0][1][0]=-prices[0]; dp[0][1][1]=-1; dp[0][1][2]=0; } //if array size is 2: else if(len>=2){ //dp[0][0][..] dp[0][0][0]=0; dp[0][0][1]=-1; dp[0][0][2]=-1; //dp[0][1][..] dp[0][1][0]=-prices[0]; dp[0][1][1]=-1; dp[0][1][2]=0; //dp[1][0][..] if(dp[0][0][0] >=dp[0][1][0]+prices[1]) { dp[1][0][0]=dp[0][0][0]; dp[1][0][1]=dp[0][0][1]; dp[1][0][2]=dp[0][0][2]; } else{ dp[1][0][0]=dp[0][1][0]+prices[1]; dp[1][0][1]=dp[0][1][2]; dp[1][0][2]=1; } //dp[1][1][..] if(dp[0][1][0]>dp[0][0][0]-prices[1]) { dp[1][1][0]=dp[0][1][0]; dp[1][1][1]=dp[0][1][1]; dp[1][1][2]=dp[0][1][2]; } else{ dp[1][1][0]=dp[0][0][0]-prices[1]; dp[1][1][1]=-1; dp[1][1][2]=1; } if(len==2){ for(i=0; i dp[i-1][1][0]+prices[i]){ last=0; dp[i][0][0]=dp[i-1][0][0]; dp[i][0][1]=dp[i-1][0][1]; dp[i][0][2]=dp[i-1][0][2]; } else{ last=1; dp[i][0][0]=dp[i-1][1][0]+prices[i]; dp[i][0][1]=dp[i-1][1][2]; dp[i][0][2]=i; } //dp[i][1][..] if(dp[i-1][1][0]>= dp[i-2][0][0]-prices[i]){ dp[i][1][0]=dp[i-1][1][0]; dp[i][1][1]=dp[i-1][1][1]; dp[i][1][2]=dp[i-1][1][2]; } else{ dp[i][1][0]=dp[i-2][0][0]-prices[i]; dp[i][1][1]=dp[i-2][0][2]; dp[i][1][2]=i; } } } //print whole array of information. int j; for(j=0; j<2; j++){ for(i=0; i sumup; prev=dp[len-1][0][1]; next=dp[len-1][0][2]; while(1){ sumup.push_back(prices[next] -prices[prev]); if (last == 1){ if(dp[prev][last][1]==-1) break; prev=dp[dp[prev][last][1]][1-last][1]; next=dp[dp[prev][last][1]][1-last][2]; } }*/ } }; int main() { vector ar={1,2,3,0,2}; Solution S; S.maxProfit(ar); return 0; }

exp