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).

分析

首先不压缩空间的写法,写法依然参照stock problem精帖的base case ,分别用一个二维数组去储存sell和buy的状况

const int inf=-999999;

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        if(prices.size()<=1)

           return 0;

        int days=prices.size();

        int sell[days+1][3],buy[days+1][3];

        for(int i=0;i<3;i++){

            sell[0][i]=0;

            buy[0][i]=inf;

        }

        for(int i=0;i<=prices.size();i++){

            sell[i][0]=0;

            buy[i][0]=inf;

        }

        for(int i=1;i<=prices.size();i++){

            for(int k=1;k<=2;k++){

                sell[i][k]=max(sell[i-1][k],buy[i-1][k]+prices[i-1]);

                buy[i][k]=max(buy[i-1][k],sell[i-1][k-1]-prices[i-1]);

            }

        }

        return sell[prices.size()][2];

    }

};