题解 | #买卖股票的最好时机(三)#

int MAX(int a,int b)
{
    if(a > b)
        return a;
    return b;
}

int maxProfit(int* prices, int pricesLen ) 
{
    // write code here
    int dp[pricesLen][5];
    for(int i = 0;i < pricesLen;i++)
    {
        for(int j = 0;j < 5;j++)
        {
            dp[i][j] = -10000;//初始化dp为最小
        }
    }
    
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[0][2] = 0;
    for(int i = 1;i < pricesLen;i++)
    {
        dp[i][0] = dp[i-1][0];                           //dp[i][0]表示到第i天为止没有买过股票的最大收益
        dp[i][1] = MAX(dp[i-1][1],dp[i-1][0]-prices[i]); //dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益
        dp[i][2] = MAX(dp[i-1][2],dp[i][1]+prices[i]);   //dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益
        dp[i][3] = MAX(dp[i-1][3],dp[i-1][2]-prices[i]); //dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益
        dp[i][4] = MAX(dp[i-1][4],dp[i-1][3]+prices[i]); //dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益
    }
    //最后我们还要从0、第一次卖出、第二次卖出中选取最大值，因为有可能没有收益，也有可能只交易一次收益最大。
    int back = MAX( MAX(dp[pricesLen-1][2],dp[pricesLen-1][4]),0 );
    return back;
}