题解 | #股票交易的最大收益（二）#

dp

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        if(prices.size() == 0) return 0;
        int n = prices.size();
        int dp[n][3][2];
        memset(dp, 0, sizeof(dp));

        for(int i = 0; i < n; i ++){
            for(int k = 1; k < 3; k ++){
                if(i == 0){
                    dp[0][k][0] = 0;
                    dp[0][k][1] = INT_MIN;
                    if(k == 1) dp[0][1][1] = -prices[i];
                    continue;
                }
                if(k == 0){
                    dp[i][0][0] = 0;
                    dp[i][0][1] = INT_MIN;
                    continue;
                }
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return max(dp[n - 1][1][0], dp[n - 1][2][0]);
    }
};