A.每日一题——3652. 按策略买卖股票的最佳时机
题目链接：3652. 按策略买卖股票的最佳时机（中等）
算法原理：
解法一：前缀和+定长滑动窗口
14ms击败5.74%
时间复杂度O(N)
①核心思路：max(不修改时的利润，修改后能得到的最大利润)
以下prices[i]用p[i]表示，strategy[i]用s[i]表示
②修改后能得到的最大利润：通过定长滑动窗口获得，因为长度为k的滑动窗口中，前k/2为0，后k/2为1，前k/2与s数组相乘后为0，故只取后k/2的利润
③定义前缀和和后缀和：快速获得窗口前部分和窗口后部分不修改时能获得的利润
注意防止p数组和s数组索引越界访问，所以定义如下👇
//保证索引1~index long[] prev=new long[n+1];//前缀和 long[] suff=new long[n+2];//后缀和 //前缀和prev[i]:i之前的前缀和，不包括i for(int i=1;i<=n;i++) prev[i]=prev[i-1]+p[i-1]*s[i-1]; //后缀和suff[i]:i-1之后的后缀和，包括i-1 //统一含义：后缀和suff[i]:i-2之后的后缀和，不包括i-2 for(int i=n;i>=1;i--) suff[i]=suff[i+1]+p[i-1]*s[i-1];其中：suff[right+2] → 原数组 (right+2)-1 = right+1 ~ n-1（正好是窗口 right 号之后的元素，不含窗口 right 号）
以防有些小伙伴看不懂索引的对应关系，博主下面附上了手画图解，便于理解👇
④定长滑动窗口获得窗口内修改后能获得的利润：
进窗口：sum累加窗口内能获得时的利润
窗口后k/2部分的利润=sum-前k/2部分的利润
更新：max（不修改时的利润，修改后拼接三个部分[0,left-1][left,right][right+1,n-1]的利润）
出窗口：left出窗口
⑤小优化：注意，在统计窗口内前k/2部分利润的时候，用循环计算会导致时间复杂度变成O(nk)，在LeetCode会超时，因此需要预处理p数组的前缀和来优化，用前缀和相减的方式在O(1)的时间复杂度下快速统计
解法二：前缀和
7ms击败44.13%
时间复杂度O(N)
图解如下👇
①遍历每个i，在i后面取个长度为k的区间 [i-k,i-1]（不往前取是防止越界，且取后面好分析）利用前缀和来解
②定义sum[i]：p[i]*s[i]的前缀和，不包括i位置
定义sumsell[i]：p[i]的前缀和，不包括i位置
那么不修改时的总利润自然为sum[n]
③其余如上图解，修改时取到的最大利润为三个部分的总和：
sum[i-k]+sum[n]-sum[i]+sumsell[i]-sumsell[i-k/2]
④注意：ret初始化为最小值Long.MIN_VALUE,因为可能出现负数，LeetCode的测试用例会导致初始化为-0x3f3f3f3f也不能通过的
解法三：滑动窗口
5ms击败89.54%
时间复杂度O(N)
设不修改时利润total，相比不修改时利润增加了sum，因为最大利润maxsum可能是负数，所以返回值为 total+max(maxsum,0)
滑动窗口[i-k,i-1]找maxsum的过程中：
左半窗口：[i-k,i-k/2-1]，修改前策略为s[i]，修改后策略为0，利润增加p[j]*(0-s[j])之和，j在左半窗口
右半窗口：[i-k/2,i-1]，修改前策略为s[i]，修改后策略为1，利润增加p[j]*(1-s[j])之和，j在右半窗口
所以窗口滑动时，有窗口首位置、尾位置和中间位置改变
首位置进窗口：sum增加了p[i]*(1-s[i])
中间位置i-k/2的元素更新：从右半窗口移到左半窗口，s数组值从1变成0，sum减少了p[i-k/2]
尾位置出窗口：sum减少了p[i-k]*(-s[i-k])
Java代码：
class Solution { //解法一优化前的代码 public long maxProfit(int[] p, int[] s, int k) { int n=p.length; //先计算不修改时的最大利润 long total=0; for(int i=0;i<n;i++) total+=p[i]*s[i]; //计算修改后能获得的最大利润 //保证索引1~index long[] prev=new long[n+1];//前缀和 long[] suff=new long[n+2];//后缀和 //前缀和prev[i]:i之前的前缀和，不包括i for(int i=1;i<=n;i++) prev[i]=prev[i-1]+p[i-1]*s[i-1]; //后缀和suff[i]:i-1之后的后缀和，包括i-1 //统一含义：后缀和suff[i]:i-2之后的后缀和，不包括i-2 for(int i=n;i>=1;i--) suff[i]=suff[i+1]+p[i-1]*s[i-1]; long ret=total,sum=0; for(int right=0;right<n;right++){ //进窗口 sum+=p[right]; int left=right-k+1; if(left<0) continue; //更新 //计算窗口内的前k/2个和 long prevsum=0; for(int i=left;i<left+k/2;i++) prevsum+=p[i]; //计算窗口内的后k/2个和 long suffsum=sum-prevsum; //拼接三个部分[0,left-1][left,right][right+1,n-1] long tmp=suffsum+prev[left]+suff[right+2]; //不修改和修改后能拿的最大利润取最大值 ret=Math.max(ret,tmp); //出窗口 sum-=p[left]; } return ret; } }class Solution { //解法一优化后的代码 public long maxProfit(int[] p, int[] s, int k) { int n=p.length; //先计算不修改时的最大利润 long total=0; for(int i=0;i<n;i++) total+=p[i]*s[i]; //计算修改后能获得的最大利润 //保证索引1~index long[] prev=new long[n+1];//前缀和 long[] suff=new long[n+2];//后缀和 //前缀和prev[i]:i之前的前缀和，不包括i for(int i=1;i<=n;i++) prev[i]=prev[i-1]+p[i-1]*s[i-1]; //后缀和suff[i]:i-1之后的后缀和，包括i-1 //统一含义：后缀和suff[i]:i-2之后的后缀和，不包括i-2 for(int i=n;i>=1;i--) suff[i]=suff[i+1]+p[i-1]*s[i-1]; long ret=total,sum=0; //优化：预处理区间和 long[] prefix=new long[n+1]; //prefix[i]:i之前的前缀和,不包括i for(int i=1;i<=n;i++) prefix[i]=prefix[i-1]+p[i-1]; for(int right=0;right<n;right++){ //进窗口 sum+=p[right]; int left=right-k+1; if(left<0) continue; //更新 //计算窗口内的前k/2个和 //优化：用前缀和相减代替原本的遍历 long prevsum=prefix[left+k/2]-prefix[left]; //计算窗口内的后k/2个和 long suffsum=sum-prevsum; //拼接三个部分[0,left-1][left,right][right+1,n-1] long tmp=suffsum+prev[left]+suff[right+2]; //不修改和修改后能拿的最大利润取最大值 ret=Math.max(ret,tmp); //出窗口 sum-=p[left]; } return ret; } }class Solution { //解法二：单纯前缀和解法 public long maxProfit(int[] p, int[] s, int k) { int n=p.length; long[] sum=new long[n+1]; long[] sumsell=new long[n+1]; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+p[i-1]*s[i-1]; sumsell[i]=sumsell[i-1]+p[i-1]; } long ret=Long.MIN_VALUE;//可能出现负数 for(int i=k;i<=n;i++) ret=Math.max(ret,sum[i-k]+sum[n]-sum[i]+sumsell[i]-sumsell[i-k/2]); return Math.max(sum[n],ret); } }class Solution { //解法三：滑动窗口 public long maxProfit(int[] p, int[] s, int k) { long total=0,maxsum=0,sum=0; for(int i=0;i<p.length;i++){ //计算不修改时的最大利润 total+=p[i]*s[i]; //进窗口 sum+=p[i]*(1-s[i]); //还未形成窗口时 if(i<k-1){ //在下一轮循环中，中间下标的元素从右半部分移到左半部分，s[i-k/2+1]从1变成0 if(i>=k/2-1) sum-=p[i-k/2+1]; continue; } //更新 maxsum=Math.max(maxsum,sum); //出窗口 //中间下标i-k/2+1元素右半部分移到左半部分，s[i-k/2+1]从1变成0 //尾下标i-k+1元素出窗口 sum-=p[i-k/2+1]-p[i-k+1]*s[i-k+1]; } return total+maxsum; } }