描述

假設你有一個數(shù)組，它的第i個元素是一支給定的股票在第i天的價格。設計一個算法來找到最大的利潤。你最多可以完成兩筆交易。

樣例

給出一個樣例數(shù)組 [4,4,6,1,1,4,2,5], 返回 6

思路：

分為五個階段，如下圖所示。

股票3.png

考慮dp[n][k]為前n支股票在階段k能獲得的最大利潤。
如果k為1，3，5，意味著此時并沒有持有股票。那么前一狀態(tài)n-1支股票只有兩種取法，一種是前n-1支股票本來就在k的位置，即遍歷到前n-1支股票仍然沒有股票，沒有利潤，因此dp[n][k]=dp[n-1][k]。另一種是n-1時持有股票，即必然處于k-1的狀態(tài)，到n時正好賣出，即dp[n][k]=dp[n-1][k-1]+prices[n-1]-prices[n-2]。二者取最大值。
如果k為2，4，意味此時持有股票。那么前一狀態(tài)n-1支股票有三種取法。
1.前n-1支股票也處于狀態(tài)k，則此時利潤為dp[n][k]=dp[n-1][k]+prices[n-1]-prices[n-2]。
2.前n-1支股票處于狀態(tài)k-1，沒有股票，則在n-1時刻買入，此時dp[n][k]=dp[n-1][k-1]。
3.前n-1支股票處于狀態(tài)k-2，即第一次持有股票，賣出去后再買入當天的股票，此時dp[n][k]=dp[n-1][k-2]+prices[n-1]-prices[n-2]。
三者取最大值。
結果返回沒有持有股票時候的最大值就行了。具體實現(xiàn)如下。

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        int n=prices.size();
        if(!n)
        {
            return 0;
        }
        vector<vector<int>> dp(n+1,vector<int>(6,0));
        dp[0][1]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=5;j+=2)
            {
                dp[i][j]=dp[i-1][j];
                if(j-1>0 && i>=2)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+prices[i-1]-prices[i-2]);
                }
            }
            for(int j=2;j<=5;j+=2)
            {
                dp[i][j]=dp[i-1][j-1];
                if(i>=2)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j]+prices[i-1]-prices[i-2]);
                }
                if(j-2>0 && i>=2)
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-2]+prices[i-1]-prices[i-2]);
                }
            }
        }
        return max(dp[n][1],max(dp[n][3],dp[n][5]));
        
    }
};