3652. 使用策略买卖股票的最佳时机

Medium

题目描述

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

prices[i] 是第 i 天给定股票的价格。
strategy[i] 表示第 i 天的交易操作，其中：
- -1 表示买入一单位股票。
- 0 表示持有股票。
- 1 表示卖出一单位股票。

还给定一个偶数 k，你最多可以对策略进行一次修改。修改包括：

在策略中选择恰好 k 个连续元素。
将前 k/2 个元素设为 0（持有）。
将后 k/2 个元素设为 1（卖出）。

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

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

注意：对预算或股票持有没有约束，因此无论过去的操作如何，所有买卖操作都是可行的。

示例 1：

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

输出：10

解释：通过修改子数组 [0, 1] 获得最大利润 10。

示例 2：

输入：prices = [5,4,3]，strategy = [1,1,0]，k = 2

输出：9

解释：不进行任何修改即可获得最大利润 9。

约束条件：

2 <= prices.length == strategy.length <= 10^5
1 <= prices[i] <= 10^5
-1 <= strategy[i] <= 1
2 <= k <= prices.length
k 是偶数

解题思路

这道题的核心思路是通过前缀和快速计算修改某个长度为 k 的子数组对利润的影响。

算法思路：

计算基础利润：首先计算原始策略的总利润作为基准。
枚举所有可能的修改区间：对于每个长度为 k 的子数组，计算将其修改为前半部分为 0，后半部分为 1 的利润变化。
利用前缀和优化：为了快速计算区间内价格总和，我们使用前缀和数组。对于区间 [i, i+k-1]：
- 原利润 = strategy[i] * prices[i] + ... + strategy[i+k-1] * prices[i+k-1]
- 新利润 = 0 * prices[i] + ... + 0 * prices[i+k/2-1] + 1 * prices[i+k/2] + ... + 1 * prices[i+k-1]
- 利润差值 = 新利润 - 原利润
计算利润差值：
- 移除原策略的贡献：-sum(strategy[i:i+k] * prices[i:i+k])
- 添加新策略的贡献：sum(prices[i+k/2:i+k])（后半部分设为1）

通过遍历所有可能的起始位置，找到能产生最大利润增益的修改方案。

时间复杂度：O(n)，其中 n 是数组长度。 空间复杂度：O(n)，用于存储前缀和数组。

代码实现

class Solution {
public:
    long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) {
        int n = prices.size();
        
        // Calculate base profit
        long long baseProfit = 0;
        for (int i = 0; i < n; i++) {
            baseProfit += (long long)strategy[i] * prices[i];
        }
        
        // Prefix sum for prices
        vector<long long> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + prices[i];
        }
        
        long long maxProfit = baseProfit;
        
        // Try every segment of length k
        for (int i = 0; i <= n - k; i++) {
            // Calculate original profit for this segment
            long long originalSegmentProfit = 0;
            for (int j = i; j < i + k; j++) {
                originalSegmentProfit += (long long)strategy[j] * prices[j];
            }
            
            // New profit: first k/2 elements are 0, last k/2 elements are 1
            long long newSegmentProfit = prefixSum[i + k] - prefixSum[i + k / 2];
            
            // Calculate profit delta
            long long delta = newSegmentProfit - originalSegmentProfit;
            
            maxProfit = max(maxProfit, baseProfit + delta);
        }
        
        return maxProfit;
    }
};

class Solution:
    def maxProfit(self, prices: List[int], strategy: List[int], k: int) -> int:
        n = len(prices)
        
        # Calculate base profit
        base_profit = sum(strategy[i] * prices[i] for i in range(n))
        
        # Prefix sum for prices
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + prices[i]
        
        max_profit = base_profit
        
        # Try every segment of length k
        for i in range(n - k + 1):
            # Calculate original profit for this segment
            original_segment_profit = sum(strategy[j] * prices[j] for j in range(i, i + k))
            
            # New profit: first k/2 elements are 0, last k/2 elements are 1
            new_segment_profit = prefix_sum[i + k] - prefix_sum[i + k // 2]
            
            # Calculate profit delta
            delta = new_segment_profit - original_segment_profit
            
            max_profit = max(max_profit, base_profit + delta)
        
        return max_profit

public class Solution {
    public long MaxProfit(int[] prices, int[] strategy, int k) {
        int n = prices.Length;
        
        // Calculate base profit
        long baseProfit = 0;
        for (int i = 0; i < n; i++) {
            baseProfit += (long)strategy[i] * prices[i];
        }
        
        // Prefix sum for prices
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + prices[i];
        }
        
        long maxProfit = baseProfit;
        
        // Try every segment of length k
        for (int i = 0; i <= n - k; i++) {
            // Calculate original profit for this segment
            long originalSegmentProfit = 0;
            for (int j = i; j < i + k; j++) {
                originalSegmentProfit += (long)strategy[j] * prices[j];
            }
            
            // New profit: first k/2 elements are 0, last k/2 elements are 1
            long newSegmentProfit = prefixSum[i + k] - prefixSum[i + k / 2];
            
            // Calculate profit delta
            long delta = newSegmentProfit - originalSegmentProfit;
            
            maxProfit = Math.Max(maxProfit, baseProfit + delta);
        }
        
        return maxProfit;
    }
}

var maxProfit = function(prices, strategy, k) {
    const n = prices.length;
    
    // Calculate base profit
    let baseProfit = 0;
    for (let i = 0; i < n; i++) {
        baseProfit += strategy[i] * prices[i];
    }
    
    // Prefix sum for prices
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + prices[i];
    }
    
    let maxProfitValue = baseProfit;
    
    // Try every segment of length k
    for (let i = 0; i <= n - k; i++) {
        // Calculate original profit for this segment
        let originalSegmentProfit = 0;
        for (let j = i; j < i + k; j++) {
            originalSegmentProfit += strategy[j] * prices[j];
        }
        
        // New profit: first k/2 elements are 0, last k/2 elements are 1
        const newSegmentProfit = prefixSum[i + k] - prefixSum[i + Math.floor(k / 2)];
        
        // Calculate profit delta
        const delta = newSegmentProfit - originalSegmentProfit;
        
        maxProfitValue = Math.max(maxProfitValue, baseProfit + delta);
    }
    
    return maxProfitValue;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	分析
时间复杂度	O(n × k)，其中 n 是数组长度。需要遍历所有长度为 k 的子数组，每次计算原始利润需要 O(k) 时间
空间复杂度	O(n)，用于存储价格的前缀和数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析