会超时
by xiaosi4081 @ 2023-11-14 13:17:46
时间复杂度大于 $O(n^2)$ ，在此题中通过不了
by xiaosi4081 @ 2023-11-14 13:19:24
@[xiaosi4081](/user/343531) 在输入
```
5
1 0 0 1 0
```
时会输出14,求大佬帮忙改一改
by CE_TAP @ 2023-11-14 13:19:53
请使用前缀和思想通过此题
by xiaosi4081 @ 2023-11-14 13:20:25
```c++
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int peo[n]= {0};
for(int i=0; i<n; i++) {
cin>>peo[i];
}
int boy=0,gir=0,max=0; //在main函数内没有赋初值的话默认为差不多2000000的一个数，看编译器
for(int i=0; i<n; i++) {
boy=0,gir=0;
for(int j=i+1; j<n; j++) {
for(int k=i; k<=j; k++) { //遍历
if(peo[k]==1) {
//当检测到女生
gir++;
}
if(peo[k]==0) {
//当检测到男生
boy++;
}
}
if(boy==gir) {
if(max<gir+boy) {
max=gir+boy;
}
}
}
}
cout<<max<<endl; //将输出移出来
}
```
by xiaosi4081 @ 2023-11-14 13:22:30
@[xiaosi4081](/user/343531) 现在AC是AC了
但有些点超时了
麻烦大佬教蒟蒻前缀和
## 代码如下
```cpp
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int peo[n]= {0};
for(int i=0; i<n; i++) {
cin>>peo[i];
}
int boy=0,gir=0,max=0; //在main函数内没有赋初值的话默认为差不多2000000的一个数，看编译器
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
for(int k=i; k<=j; k++) { //遍历
if(peo[k]==1) {
//当检测到女生
gir++;
}
if(peo[k]==0) {
//当检测到男生
boy++;
}
}
if(boy==gir) {
if(max<(gir+boy)) {
max=gir+boy;
}
}boy=0,gir=0;
}
}
cout<<max<<endl; //将输出移出来
}
```
by CE_TAP @ 2023-11-14 13:32:48
@[CE_TAP](/user/1055118) https://oi-wiki.org/basic/prefix-sum/
by wangyinghao @ 2023-11-14 13:38:46
@[CE_TAP](/user/1055118) 还有这道题中要用到差的思想
by xiaosi4081 @ 2023-11-14 13:43:09