3573：买卖股票的最佳时机 V（1777 分）

Ian

2025-06-07 约 691 字预计阅读 2 分钟次阅读

力扣第 158 场双周赛第 2 题

题目

给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。

你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：

普通交易：在第 i 天买入，然后在之后的第 j 天卖出，其中 i < j。你的利润是 prices[j] - prices[i]。
做空交易：在第 i 天卖出，然后在之后的第 j 天买回，其中 i < j。你的利润是 prices[i] - prices[j]。

注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。

通过进行最多 k 笔交易，返回你可以获得的最大总利润。

示例 1:

输入: prices = [1,7,9,8,2], k = 2

输出: 14

解释:

我们可以通过 2 笔交易获得 14 美元的利润：

一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。
一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。

示例 2:

输入: prices = [12,16,19,19,8,1,19,13,9], k = 3

输出: 36

解释:

我们可以通过 3 笔交易获得 36 美元的利润：

一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。
一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。
一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。

提示:

2 <= prices.length <= 10³
1 <= prices[i] <= 10⁹
1 <= k <= prices.length / 2

相似问题：

0121：买卖股票的最佳时机

分析

#1

类似 0188，只是多了个卖出状态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        f = [[0,-inf,-inf] for _ in range(k+1)]
        for x in prices:
            for i in range(k,-1,-1):
                f[i][1] = max(f[i][1],f[i][0]-x)
                f[i][2] = max(f[i][2],f[i][0]+x)
                if i:
                    f[i][0] = max(f[i][0],f[i-1][1]+x,f[i-1][2]-x)
        return f[-1][0]

1691 ms

#2

类似的，也可以用 wqs 二分优化

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        def cal(x):                 # 选一个的额外代价是x时，最大收益s及对应最小次数c
            f,g,h = (0,0),(-inf,0),(-inf,0)
            for a in prices:
                f,g,h = max(f,(g[0]+a-x,g[1]-1),(h[0]-a-x,h[1]-1)),max(g,(f[0]-a,f[1])),max(h,(f[0]+a,f[1]))
            return f[0],-f[1]

        l, r = 0, max(prices)
        res = 0
        while l<=r:
            mid = (l+r)//2
            s,c = cal(mid)
            if c<=k:
                res = s+k*mid
                r = mid-1
            else:
                l = mid+1
        return res

499 ms

目录

3573：买卖股票的最佳时机 V（1777 分）

题目

分析

#1

#2

解答