大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题目要求在最多进行k次买卖的情况下计算农场主人能获得的最大利润。每次买卖包括一次买入和一次卖出，而且在买入新的牛之前必须已经卖掉手头上的牛。

为了解决这个问题，我们可以使用动态规划来计算最大利润。我们需要定义一个二维数组 dp[i][j]，表示在第 i 天进行了 j 次买卖后的最大利润。然后，我们遍历数组中的每个价格，并根据动态规划的状态转移方程来更新利润。

具体解答步骤如下：

  1. 初始化二维数组 dp，大小为 k + 1 行，prices.size() 列。其中，dp[i][j] 表示在第 i 天进行了 j 次买卖后的最大利润，初始值为0。
  2. 对于第一行 dp[0][j]，表示在第 0 天（即还未开始买卖）进行了 j 次买卖后的最大利润，初始值为0。
  3. 对于第一列 dp[i][0]，表示在任意一天进行了 0 次买卖后的最大利润，初始值为0。
  4. 遍历数组中的每个价格 prices[i]，对于每个价格，我们需要更新 dp[i][j] 的值。具体更新方式如下：不进行买卖：dp[i][j] = dp[i-1][j]，即当天不进行买卖，利润与前一天的利润相同。进行买卖：dp[i][j] = max(dp[i][j], dp[i-1][j-1] + prices[i] - prices[i-1])，即当天进行买卖，利润为前一天进行 j-1 次买卖后的利润，加上今天的价格与昨天的价格之差。
  5. 最终的结果为 dp[prices.size()-1][k]，表示在最后一天进行了 k 次买卖后的最大利润。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxProfitII(vector<int>& prices, int k) {
        int n = prices.size();
        if (k == 0 || n < 2) {
            return 0;
        }

        // 如果 k 大于等于数组长度的一半，相当于可以进行无限次买卖
        // 这种情况下可以转化为不限制次数的买卖问题，直接返回最大利润即可
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        vector<vector<int>> dp(k + 1, vector<int>(n, 0));
        for (int i = 1; i <= k; ++i) {
            int maxDiff = -prices[0];  // 保存第 i 次买入后的最大利润
            for (int j = 1; j < n; ++j) {
                dp[i][j] = max(dp[i][j - 1], prices[j] + maxDiff);
                maxDiff = max(maxDiff, dp[i - 1][j] - prices[j]);
            }
        }

        return dp[k][n - 1];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！