Problem

You are given an integer array prices where prices[i] is the price of a given stock on the iᵗʰ day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

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

Test Cases

1
2
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pytest

from solution import Solution


@pytest.mark.parametrize('k, prices, expected', [
    (2, [2,4,1], 2),
    (2, [3,2,6,5,0,3], 7),

    (2, [1], 0),
])
@pytest.mark.parametrize('sol', [Solution()])
class Test:
    def test_solution(self, sol, k, prices, expected):
        assert sol.maxProfit(k, prices) == expected

Thoughts

同系列问题：

本题是交易至多指定的 k 次。

在 123. Best Time to Buy and Sell Stock III 中特别定义了 动态规划的状态及其转移函数，虽然对那道题的帮助不是很大，但稍加扩展就可以直接应用于本题。

定义 buy(i, j) 表示在第 i 天结束前，（至少买入 1 次）至多买入 j 次，最大的现金余额（同样设可以借钱买股票，初始余额为 0），sell(i, j) 表示在第 i 天结束前，至多卖出 j 次，最大的现金余额。

显然 buy(i, 1) = buy1(i)，buy(i, 2) = buy2(i)，sell(i, 1) = sell1(i)，sell(i, 2) = sell2(i)。

递推关系也类似地调整为：

{buy1,j=−prices[0]sell1,j=0buyi,1=max⁡{buyi−1,j,−prices[i]}buyi,j=max⁡{buyi−1,j,selli−1,j−1−prices[i]}selli,j=max⁡{selli−1,j,buyi−1,j+prices[i]}\begin{cases} buy_{1,j}=-prices[0] \\ sell_{1,j}=0 \\ buy_{i,1}=\max\{buy_{i-1,j},-prices[i]\} \\ 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]\} \end{cases}

同样只需要保留前一天的 k 对 buy 和 sell 值即可。

小心 k-刺客：如果有 n 天，则最多可以交易 ⌊n/2⌋\lfloor n/2\rfloor 次。如果给定的 k 过大，可以先把 k 改成 ⌊n/2⌋\lfloor n/2\rfloor。另外如果 k 是 0，直接返回 0 即可。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
min2 = lambda a, b: a if a <= b else b
max2 = lambda a, b: a if a >= b else b


class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        k = min2(k, len(prices) >> 1)
        if k == 0: return 0
        buys = [-prices[0]] * k
        sells = [0] * k
        for price in prices:
            prev_sell = 0
            for j in range(k):
                prev_sell, buys[j], sells[j] = (
                    sells[j],
                    max2(buys[j], prev_sell - price),
                    max2(sells[j], buys[j] + price),
                )

        return sells[-1]
hard
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~