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

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int solve(vector<int>& prices, int k) {
        //dp[i][0]，表示第i次买入操作收益
        //dp[i][1]，表示第i次卖出操作收益
        vector<vector<int>> dp(k, vector<int>(2, 0)); 
        
        for(int i = 0; i < k; ++i) {
            dp[i][0] = -prices[0];
        }
        
        for (int i = 1; i < (int)prices.size(); ++i) {
            for (int j = 0; j < k; ++j) {
                if (j == 0) {
                    dp[j][0] = max(dp[j][0], -prices[i]);          //在第i天进行第1次买入操作，最大收益
                    dp[j][1] = max(dp[j][1], dp[j][0] + prices[i]);//在第i天进行第1次卖出操作，最大收益
                } else {
                    dp[j][0] = max(dp[j][0], dp[j-1][1] - prices[i]);//在第i天进行第j次买入操作，最大收益
                    dp[j][1] = max(dp[j][1], dp[j][0] + prices[i]);  //在第i天进行第j次卖出操作，最大收益
                }
            }
        }
        
        return dp[k-1][1] > 0 ? dp[k-1][1] : 0;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> prices(n, 0);
    for (int i = 0; i < n; ++i)
        cin >> prices[i];
    
    Solution * s = new Solution();
    int ret = s->solve(prices, k);
    cout << ret << endl;
    
    return 0;
        
}