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

题目描述#

给你两个整数数组 prices 和 strategy，其中：

prices[i] 表示第 i 天某股票的价格。
strategy[i] 表示第 i 天的交易策略：
- -1 表示买入一单位股票
- 0 表示持有股票
- 1 表示卖出一单位股票

同时给你一个偶数整数 k，你可以对 strategy 进行最多一次修改。一次修改包括：

选择 strategy 中恰好 k 个连续元素；
将前 k / 2 个元素设为 0；
将后 k / 2 个元素设为 1。

利润定义为所有天数中 strategy[i] * prices[i] 的总和。

请返回可以获得的最大可能利润。

注意：

没有预算限制；
没有股票持有数量限制；
所有买入和卖出操作都一定可行；
不需要考虑过去的操作是否合法，只需要按照题目给定公式计算总利润。

知识边界#

这道题本质上是一个前缀和 + 枚举连续区间的问题，而不是传统意义上的股票动态规划问题。

1. 前缀和#

前缀和用于快速计算区间和。

如果定义：

prefix[i]

表示前 i 个元素的和，那么区间 [l, r) 的和就是：

prefix[r] - prefix[l]

在本题中，代码里构造了两个前缀和数组：

`prefix`#

表示原始策略下的利润前缀和：

prefix[i+1] = prefix[i] + strategy[i]*prices[i]

这样：

prefix[0] = 0
prefix[n] 就是原始总利润
某段区间的原始利润可以通过前缀和快速求出

`sumSell`#

表示价格数组的前缀和：

sumSell[i+1] = sumSell[i] + prices[i]

它的作用是：当某一段被全部修改为卖出，也就是 strategy = 1 时，这段区间的新利润就等于这段价格之和。

2. 连续区间枚举#

题目要求必须选择恰好 k 个连续元素进行修改，因此可以枚举每一个长度为 k 的区间。

如果枚举变量 i 表示区间右端点，那么：

区间是 [i-k, i)
前半段是 [i-k, i-k/2)
后半段是 [i-k/2, i)

这是代码中的核心枚举方式：

for i := k; i <= len(prices); i++ {
}

这样可以保证所有长度为 k 的连续区间都被枚举到，而且不会越界。

3. 区间修改后的贡献计算#

对于一个被选中的长度为 k 的区间：

前 k/2 个元素全部改成 0
后 k/2 个元素全部改成 1

所以：

前半段贡献变成 0
后半段贡献变成对应价格和

这正是代码里这部分的含义：

sumSell[i] - sumSell[i-k/2]

它表示后半段 [i-k/2, i) 的价格总和。

4. Go 中数组和切片的下标习惯#

Go 中通常使用前缀和数组长度为 n+1，其中：

prefix[0] = 0
原数组下标是 0 到 n-1
前缀和下标是 0 到 n

这种写法能统一表示区间 [l, r) 的和，避免边界分类讨论。

5. Go 语言中的辅助函数#

用户给出的代码里使用了：

ans = max(ans, res)

因此需要提供一个 max 函数。

Go 没有内置整数 max 函数（如果不使用特定版本新增能力），常见写法如下：

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

6. 常见错误点#

错误一：把前半段也算入收益#

前半段被修改成 0，所以贡献是 0，不能再保留原本的利润。

错误二：后半段仍然按原策略计算#

后半段被强制设为 1，所以贡献应该是价格本身，而不是 strategy[i] * prices[i]。

错误三：区间边界写错#

枚举 [i-k, i) 时，后半段是 [i-k/2, i)，这里非常容易写成错误的边界，必须严格对应代码中的下标关系。

思路#

先计算原始策略下的总利润，然后枚举所有长度为 k 的连续区间，假设对当前区间执行修改，计算修改后的总利润，取最大值即可。

思路一#

定义：

prefix[i]：前 i 天原始利润之和
sumSell[i]：前 i 天价格之和

原始总利润是：

prefix[len(prices)]

假设当前枚举的修改区间是 [i-k, i)，那么修改后的利润由三部分组成：

左边未修改部分 [0, i-k) 的利润：
```
prefix[i-k]
```
右边未修改部分 [i, n) 的利润：
```
prefix[len(prices)] - prefix[i]
```
修改区间中的新利润：
- 前半段 [i-k, i-k/2) 全部变成 0，贡献为 0
- 后半段 [i-k/2, i) 全部变成 1，贡献为：
```
sumSell[i] - sumSell[i-k/2]
```

因此总利润就是：

res := prefix[i-k] + prefix[len(prices)] - prefix[i] + sumSell[i] - sumSell[i-k/2]

然后不断更新最大值。

为什么这样做是正确的#

因为一次修改只影响一个长度恰好为 k 的连续区间，区间外的利润完全不变。

而区间内部又按题意被固定分成两部分：

前半部分改为 0
后半部分改为 1

因此每个候选区间修改后的利润都可以被准确表示为：

左侧原利润
右侧原利润
后半段新的卖出收益

枚举所有可能区间后，最大值就是答案。

时间复杂度#

构造前缀和：O(n)
枚举所有长度为 k 的区间：O(n)

总时间复杂度为：

O(n)

空间复杂度#

使用了两个长度为 n+1 的前缀和数组：

O(n)

代码#

package main

func maxProfit(prices []int, strategy []int, k int) int64 {
	prefix := make([]int, len(prices)+1)
	sumSell := make([]int, len(prices)+1)
	for i := 0; i < len(prices); i++ {
		prefix[i+1] = prefix[i] + strategy[i]*prices[i]
		sumSell[i+1] = sumSell[i] + prices[i]
	}
	ans := prefix[len(prices)]
	for i := k; i <= len(prices); i++ {
		res := prefix[i-k] + prefix[len(prices)] - prefix[i] + sumSell[i] - sumSell[i-k/2]
		ans = max(ans, res)
	}
	return int64(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}