观察输入样例可以发现
题目要求求长度为 n2/2上取整的连续子数组的最大和。
然后用前缀和做就行了
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int p[N];
int main()
{ int t;
cin>>t;
int res=1;
while(t--)
{ int n;
string s="";
cin>>n;
cin>>s;
for(int i=0;i<n;i++)
p[i+1]=s[i]-48;
for(int i=1;i<=n;i++)
p[i]=p[i]+p[i-1];
int k=n%2 ? n/2+1 :n/2;
int ans=0;
for(int i=1,j=k;j<=n;j++,i++)
ans=max(ans,p[j]-p[i-1]);
printf("Case #%d: %d\n",res++,ans);
}
return 0;
}