C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-01-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int maxProfit(vector<int>& prices, int k) {
        // write code here
        int n = prices.size();
        if (n <= 1) {
            return 0;
        }
        k = min(n / 2, k);
        vector<int> lose(k + 1, 0);
        vector<int> get(k + 1, -prices[0]);
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                lose[j] = max(lose[j], get[j] + prices[i]);
                get[j] = max(get[j], lose[j - 1] - prices[i]);
            }
        }
        return lose[k];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2021-12-29

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int maxProfit(vector<int>& p, int k) {
        int n = p.size();
        if (n == 0 || k == 0) return 0;
        /*
        5个状态：
        1）不操作
        2）第一次购买b1
        3）第一次卖出s1
        4）第二次购买b2
        5）第二次卖出s2
        dp[i][j]代表第i天状态为j时产生的最大收益
        */
//         int b1,b2,s1,s2; // 分别维护第一次、第二次交易买卖的最大利润
//         b1 = b2 = -p[0], s1 = s2 = 0;
        vector<int> buy(k,-p[0]);
        vector<int> sell(k,0);
        for (auto i : p) {
            buy[0] = max(buy[0],-i);
            sell[0] = max(sell[0],buy[0]+i);
            for(int j = 1;j<k;j++) {
                buy[j] = max(buy[j],sell[j-1]-i);
                sell[j] = max(sell[j],buy[j]+i);
            }
        }
        
        return sell[k-1];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2021-12-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int maxProfit(vector<int>& prices, int k) {
        // write code here
         vector<int> buy(k+1, INT_MIN), sell(k+1, 0);
        for (auto &j:prices) {
            for (int i = 1; i <= k; i++) {
                buy[i] = max(buy[i], sell[i-1]-j);
                sell[i] = max(sell[i], buy[i]+j);
            }
        }
        return sell[k];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-01-02

class Solution {
public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
//         获取数组长度
        if (n <= 1) return 0;
//         如果数组只有1天没有机会操作
        k = min(n / 2, k);
//         我们k的取值范围，根据我前面描述的
        vector<int> lose(k + 1, 0), get(k + 1, -prices[0]);
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                   lose[j] = max(lose[j], get[j] + prices[i]);
                   get[j] = max(get[j], lose[j - 1] - prices[i]);
            }
        }
        return lose[k];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2021-11-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int maxProfit(vector<int>& prices, int k) {
        if(prices.empty() || k == 0)return 0;
        // write code here
        vector<int> dp(2*k);
        for(int i=0;i<k;i++){
            dp[i*2+1] = -prices[0];
        }
        for(int i=1;i<prices.size();i++){
            int preno = dp[0];
            int cur = dp[1];
            dp[1] = max(dp[1], -prices[i]);
            dp[0] = max(dp[0], cur + prices[i]);
            for(int j=1;j<k;j++){
                int tem1 = dp[j*2];
                dp[j*2] = max(dp[j*2], dp[j*2+1] + prices[i]);
                dp[j*2+1] = max(dp[j*2+1], preno - prices[i]);
                preno = tem1;
            }
        }
        
        return dp[2*k-2];
    }
};