Hard

题目描述

给你一个整数数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格，和一个整数 k 。

找出你能获取的最大利润。你最多可以完成 k 笔交易：即你最多可以买 k 次，卖 k 次。

注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

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

解题思路

这是一个经典的股票买卖问题的通用版本。我们需要考虑在最多 k 次交易限制下的最大利润。

动态规划思路：

  1. 状态定义：使用 buy[i][j] 表示第 i 天进行了至多 j 次交易且当前持有股票的最大利润，sell[i][j] 表示第 i 天进行了至多 j 次交易且当前不持有股票的最大利润。

  2. 状态转移：

    • buy[i][j] = max(buy[i-1][j], sell[i-1][j-1] - prices[i])
    • sell[i][j] = max(sell[i-1][j], buy[i-1][j] + prices[i])

  3. 优化策略：

    • 当 k >= n/2 时（n为天数），相当于无限制交易，可以简化为贪心算法
    • 使用滚动数组优化空间复杂度

  4. 边界条件：第0天买入股票的利润为 -prices[0]，不持有股票的利润为0。

推荐解法：动态规划 + 空间优化，时间复杂度 O(nk)，空间复杂度 O(k)。

代码实现

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n <= 1 || k == 0) return 0;
        
        // 如果k足够大，相当于无限制交易
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i-1]) {
                    profit += prices[i] - prices[i-1];
                }
            }
            return profit;
        }
        
        // dp[j][0] 表示进行了至多j次交易且当前不持有股票的最大利润
        // dp[j][1] 表示进行了至多j次交易且当前持有股票的最大利润
        vector<vector<int>> dp(k+1, vector<int>(2, 0));
        
        for (int j = 0; j <= k; j++) {
            dp[j][1] = -prices[0];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]);
            }
        }
        
        return dp[k][0];
    }
};

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1 or k == 0:
            return 0
        
        # 如果k足够大，相当于无限制交易
        if k >= n // 2:
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    profit += prices[i] - prices[i-1]
            return profit
        
        # dp[j][0] 表示进行了至多j次交易且当前不持有股票的最大利润
        # dp[j][1] 表示进行了至多j次交易且当前持有股票的最大利润
        dp = [[0, -prices[0]] for _ in range(k+1)]
        
        for i in range(1, n):
            for j in range(k, 0, -1):
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i])
                dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i])
        
        return dp[k][0]

public class Solution {
    public int MaxProfit(int k, int[] prices) {
        int n = prices.Length;
        if (n <= 1 || k == 0) return 0;
        
        // 如果k足够大，相当于无限制交易
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i-1]) {
                    profit += prices[i] - prices[i-1];
                }
            }
            return profit;
        }
        
        // dp[j,0] 表示进行了至多j次交易且当前不持有股票的最大利润
        // dp[j,1] 表示进行了至多j次交易且当前持有股票的最大利润
        int[,] dp = new int[k+1, 2];
        
        for (int j = 0; j <= k; j++) {
            dp[j, 1] = -prices[0];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = k; j >= 1; j--) {
                dp[j, 0] = Math.Max(dp[j, 0], dp[j, 1] + prices[i]);
                dp[j, 1] = Math.Max(dp[j, 1], dp[j-1, 0] - prices[i]);
            }
        }
        
        return dp[k, 0];
    }
}

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    if (prices.length <= 1 || k === 0) return 0;
    
    if (k >= Math.floor(prices.length / 2)) {
        let profit = 0;
        for (let i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
    
    const buy = new Array(k + 1).fill(-prices[0]);
    const sell = new Array(k + 1).fill(0);
    
    for (let i = 1; i < prices.length; i++) {
        for (let j = k; j >= 1; j--) {
            sell[j] = Math.max(sell[j], buy[j] + prices[i]);
            buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);
        }
    }
    
    return sell[k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(nk)n为数组长度，k为交易次数限制，每个状态需要O(1)时间转移
空间复杂度O(k)使用二维数组存储状态，大小为(k+1)×2

相关题目