3652. 按策略买卖股票的最佳时机#

题目描述#

给定 prices 数组和 strategy 数组（-1 买入，0 持有，1 卖出）。可以至多一次将连续的 k 个策略改为：前 k/2 个变为 0（持有）、后 k/2 个变为 1（卖出）。求可得到的最大利润。

示例：

1
输入：prices = [4,2,8], strategy = [-1,0,1], k = 2
2
输出：10

解法思路#

核心思路：基础收益 + 增量。

先算出不修改策略时的基础收益：base = Σ strategy[i] * prices[i]（-1 买入记 -prices，1 卖出记 +prices，0 记 0）。

若把下标 i 的策略改成目标值，收益会变化，定义两种增量：

gain0[i]：把 strategy[i] 改成 0（持有）的收益增量 = 0 − strategy[i]·prices[i] = -strategy[i]·prices[i]
gain1[i]：把 strategy[i] 改成 1（卖出）的收益增量 = prices[i] − strategy[i]·prices[i] = (1 - strategy[i])·prices[i]

一次修改覆盖长度为 k 的连续窗口，其中前 half=k/2 个改成 0（用 gain0）、后 k/2 个改成 1（用 gain1）。于是问题转为：找长度为 k 的窗口，最大化「前半 gain0 之和 + 后半 gain1 之和」这个增量。

这正是定长滑窗：分别用两个窗长 half 的增量数组 sum_first（最左 half 个）和 sum_second（窗口右半 half 个）同步平移。最终答案 = base + max(最大增量, 0)（可以不修改，故增量下限为 0）。

逐步举例（prices=[4,2,8], strategy=[-1,0,1], k=2）：

base = -1·4 + 0·2 + 1·8 = 4
gain0 = [4, 0, -8]（改成 0 的增量）
gain1 = [8, 2, 0]（改成 1 的增量）
half = 1。初始窗口：sum_first = gain0[0] = 4，sum_second = gain1[1] = 2，增量 = 6。
解释：修改窗口 [0,1] → 策略变 [0,1,1]，收益 = 0·4 + 1·2 + 1·8 = 10，增量 = 10 − 4 = 6 ✓
取 max(6, 0)=6，ans = 4 + 6 = 10。

复杂度分析#

时间复杂度：O(n)，一次滑动。
空间复杂度：O(n)，gain0 与 gain1 数组。

代码实现#

1
class Solution:
2
    def maxProfit(self, prices: list[int], strategy: list[int], k: int) -> int:
3
        n = len(prices)
4
        half = k // 2
5

6
        base = 0
7
        gain0 = [0] * n
8
        gain1 = [0] * n
9
        for i in range(n):
10
            base += strategy[i] * prices[i]
11
            gain0[i] = -strategy[i] * prices[i]
12
            gain1[i] = (1 - strategy[i]) * prices[i]
13

14
        sum_first = sum(gain0[:half])
15
        sum_second = sum(gain1[half:k])
16
        max_gain = sum_first + sum_second
17

18
        for i in range(k, n):
19
            sum_first += gain0[i - half] - gain0[i - k]
20
            sum_second += gain1[i] - gain1[i - half]
21
            cur = sum_first + sum_second
22
            if cur > max_gain:
23
                max_gain = cur
24

25
        return base + max(max_gain, 0)

1
import sys
2
import unittest
3
from pathlib import Path
4

5
sys.path.insert(0, str(Path(__file__).parent))
6
from solution import Solution
7

8

9
class TestMaxProfit(unittest.TestCase):
10
    def setUp(self):
11
        self.solution = Solution()
12

13
    def test_example1(self):
14
        self.assertEqual(self.solution.maxProfit([4, 2, 8], [-1, 0, 1], 2), 10)
15

16
    def test_example2(self):
17
        self.assertEqual(self.solution.maxProfit([5, 4, 3], [1, 1, 0], 2), 9)
18

19
    def test_no_modification_needed(self):
20
        self.assertEqual(self.solution.maxProfit([3, 5, 2], [1, 1, 1], 2), 10)
21

22
    def test_all_buy_then_sell(self):
23
        self.assertEqual(self.solution.maxProfit([1, 2, 3, 4], [-1, -1, 1, 1], 2), 9)
24

25
    def test_k_equals_n(self):
26
        self.assertEqual(self.solution.maxProfit([1, 2], [-1, 1], 2), 2)
27

28
    def test_no_modification(self):
29
        prices = [10, 5, 15]
30
        strategy = [1, 1, 1]
31
        k = 2
32
        self.assertEqual(self.solution.maxProfit(prices, strategy, k), 30)
33

34

35
if __name__ == "__main__":
36
    unittest.main()