给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票

）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天买入，在第 2 天卖出，利润为 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天买入，在第 3 天卖出，利润为 4 。在第 5 天买入，在第 6 天卖出，利润为 3 。

提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

相关问题

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

动态规划算法：

定义状态：dp[i][j][0/1] 表示前i天交易了j次时，是否持有股票的最大利润。

状态转移方程：

- dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
- dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])

初始状态：

- dp[0][j][0] = 0
- dp[0][j][1] = INT_MIN
- dp[i][0][0] = 0
- dp[i][0][1] = INT_MIN

最终结果为：dp[n][k][0]

时间复杂度为 O(n*k)，空间复杂度为 O(n*k)。

C++ 代码如下：

class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k >= n / 2) { // 如果 k 大于等于 n/2，相当于可以进行任意多次交易，问题转化为无限次交易问题
int res = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i-1])
res += prices[i] - prices[i-1];
}
return res;
}
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(2)));
for (int i = 0; i <= k; i++) {
dp[0][i][0] = 0;
dp[0][i][1] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
dp[i][0][0] = 0;
dp[i][0][1] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1]);
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1]);
}
}
return dp[n][k][0];
}
};

.买卖股票的最佳时机 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你能选择某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。不限制买卖次数，问最大盈利，编写一个Java程序

题目可以使用贪心算法来解决。我们可以从第一天开始，如果当天的价格比前一天高，就在前一天买入，当天卖出，这样可以保证每次交易都是在最优的时机进行的。具体实现如下：

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) { // 如果当天价格高于前一天价格
            profit += prices[i] - prices[i-1]; // 在前一天买入，当天卖出
        }
    }
    return profit;
}

时间复杂度为 O(n)，空间复杂度为 O(1)。