leetcode 3652(定长滑动窗口/前缀和)

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

思路：定长滑动窗口 / 前缀和，枚举修改子数组 [i−k,i−1]

方法一：前缀和
计算两个前缀和数组：

• 定义数组 c，其中 c[i]=prices[i]⋅strategy[i]。计算 c 的前缀和，记作 sum
• 计算 prices 的前缀和，记作 sum_sell

如果不修改，答案为 sum[n]。

class Solution { public: long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) { int n=prices.size(); vector<long long> sum(n+1),sum_sell(n+1); //前缀和 for(int i=0;i<n;i++){ sum[i+1]=sum[i]+prices[i]*strategy[i]; sum_sell[i+1]=sum_sell[i]+prices[i]; } long long ans=sum[n]; for(int i=k;i<=n;i++){ long long res=sum[i-k]+sum[n]-sum[i]+sum_sell[i]-sum_sell[i-k/2]; ans=max(ans,res); } return ans; } };

方法二：定长滑动窗口

设不修改时的利润为 total。修改后，利润（相比不修改）增加了 sum (可能<0)。所有窗口的 sum 的最大值为 maxSum。那么答案为 total+max(maxSum,0)。这里可能出现 maxSum<0 的情况，此时不修改更好，也就是与 0 取最大值。

对于价格 p，如果修改前策略是 x，修改后策略是 y，那么利润增加了 p⋅(y−x)。比如原来买入，现在持有（不买入），那么利润增加了 p⋅(0−(−1))=p。又比如原来买入，现在卖出，那么利润增加了 p⋅(1−(−1))=2p。

下面计算每个窗口的 sum，考察从 [i−k,i−1] 向右滑到 [i−k+1,i]，sum 如何变化。

class Solution { public: long long maxProfit(vector<int>& prices, vector<int>& strategy, int k) { long long total=0,sum=0,max_sum=0; for(int i=0;i<prices.size();i++){ int p=prices[i],s=strategy[i]; total+=p*s; //入右半，交易策略从s变成1 sum+=p*(1-s); //2<= k <=prices.length，尚未形成第一个窗口 if(i<k-1){ if(i>=k/2-1) sum-=prices[i-k/2+1]; //形成初始窗口时的左半边元素 continue; } //更新 max_sum=max(max_sum,sum); //对于下一个窗口，下标为i-(k/2-1)的元素从右半移到左半，交易策略从 1 变成 0;下标为 i-k+1 的元素从左半离开窗口 sum-=prices[i-k/2+1]-prices[i-k+1]*strategy[i-k+1]; } return total+max_sum; } };