题解 | #风口的猪-中国牛市#

dp。

#include <vector>
class Solution {
public:
    /**
     * 计算你能获得的最大收益
     * 
     * @param prices Prices[i]即第i天的股价
     * @return 整型
     */
    int calculateMax(vector<int> prices) {
        int n = prices.size();
        stack<int> max_p;
        stack<int> min_p;
        vector<int> max_prices;
        vector<int> min_prices;
        for(int i=0;i<n;i++){
            if(min_p.empty()||min_p.top()>prices[i]) min_p.push(prices[i]);
            min_prices.push_back(min_p.top());
        }
        for(int i=n-1;i>=0;i--){
            if(max_p.empty()||max_p.top()<prices[i]) max_p.push(prices[i]);
            max_prices.push_back(max_p.top());
        }
        reverse(max_prices.begin(), max_prices.end());
        vector<vector<int>> dp(n+1, vector<int>(3,0));
        for(int i=1;i<n;i++){
            dp[i][1] = max(dp[i-1][1], prices[i]-min_prices[i]);
        }
        int max_val = 0;
        for(int i=1;i<n;i++){
            dp[i][2] = max(dp[i-1][1] + max_prices[i] - prices[i], dp[i][1]);
            max_val = max(max_val, dp[i][2]);
        }
        return max_val;
    }
};