本文主要是介绍CF 780 D. Maximum Product Strikes Back，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - D - Codeforces
题目大意：找到一个连续的区间，此区间乘积最大，区间长度0时答案为1，输出区间左边删除数量和右边删除的数量。直接输出区间不好吗？？？
解题思路：查询序列最大子段乘积，且答案至少是1，换句话说这个区间一定不包含0。
（1）先暴力思考解法，可以枚举区间左右端点[l,r]求得最大乘积，如果是正常数组，这个乘积必然超出整数范围，题目贴心地告知绝对值不大于2，因此记录最大乘积只需记录区间内2的个数。由此想到可用前缀和数组记录2和-2的个数。
（2）第二个问题，如果乘积元素中负值个数为奇数，乘积结果必然为负数。因此选择的区间负数个数必须为偶数个，怎么才能知道某个区间内负值个数呢，仍使用前缀和数组。
（3）最终解法，先找到非0区间[l,r]，此时有两种可能，一是这个区间负值个数为偶数，那么答案就是区间2和-2的个数；二是区间负值为奇数，那么或者切割到左边第一个负值，或者切割到右边第一个负值。整体时间复杂度为O（n）
CF的题目大神级解法很多，此方法代码较长。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,t,a[200005],sum[200005],sum2[200005];
main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,l,r,ans,ansl,ansr,first,last;cin>>t;while(t--){ans=0,ansl=1,ansr=0;/**< ans是最大值，[ansl,ansr]是最终答案区间 */cin>>n;sum[0]=sum2[0]=0;for(i=1; i<=n; i++){cin>>a[i];/**< 读值计算前缀和,sum2统计2和-2的个数，sum统计负数个数 */sum2[i]=sum2[i-1] + ((a[i]==2||a[i]==-2)?1:0);sum[i]=sum[i-1]+((a[i]<0)?1:0);}l=1;while(l<=n){while(a[l]==0&&l<=n)l++;if(l>n)break;r=l;while(a[r]!=0&&r<=n)r++;r--;/**< 找到非空且无0元素区间[l,r] */if((sum[r]-sum[l-1])%2==0){ /**< 区间内偶数个负数 */if((sum2[r]-sum2[l-1])>ans)ans=sum2[r]-sum2[l-1],ansl=l,ansr=r;}else{first=l,last=r;while(a[first]>0)first++;while(a[last]>0)last--; /**< 奇数个负值，找到左边第一个负数下标first，右边第一个last */if((sum2[r]-sum2[first])>ans)ans=sum2[r]-sum2[first],ansl=first+1,ansr=r;if((sum2[last-1]-sum2[l-1])>ans)ans=sum2[last-1]-sum2[l-1],ansl=l,ansr=last-1;}l=r+1;}cout<<ansl-1<<' '<<n-ansr<<endl;}return 0;
}
后记：数组名字最好区分度大一点，当你把sum2写成sum时，很难找到错误点，后果很严重.........
这篇关于CF 780 D. Maximum Product Strikes Back的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
