题意：

给出一个01串，要求只能翻转一次区间（在翻转的区间内，0变成1，1变成0），问翻转后1的数量最大是多少。

 

思路：

如果全部都为0肯定全部翻转，如果全部为1肯定只翻转一次，所以默认max应该为-1而不是-inf；

算出一段区间内0和1的个数差值cnt，与后序数字进行比较，不断更新最大值maxx和cnt。

 

AC代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<list>
 7 #include<map>
 8 #include<stack>
 9 #include<stdlib.h>
10 #include<vector>
11 #define eps 1e-9
12 #define read(x) scanf("%d",&x)
13 #define mem(a,b) memset(a,b,sizeof(a))
14 #define PI acos(-1)
15 #define F(a,b,c) for (int a=b;a<=c;a++)
16 #define RF(a,b,c) for (int a=b;a>=c;a--)
17 #define sc(a) scanf("%d",&a)
18 #define SC(n,m) scanf("%d %d",&n,&m)
19 #define pr(a) printf("%d\n",a)
20 using namespace std;
21 #define inf 0x3f3f3f3f
22 typedef long long ll;
23 
24 int a[110];
25 
26 int main()
27 {
28     int n;
29     cin>>n;
30     int sum=0,cnt=0,maxx=-1;
31     F(i,1,n)
32     {
33         int x;
34         cin>>x;
35         if(x==0)
36         {
37             cnt++;
38             maxx=max(maxx,cnt);
39         }
40         else
41         {
42             cnt--;
43             if(cnt<0)
44                 cnt=0;
45         }
46         if(cnt<maxx||!cnt)
47             sum+=x;
48     }
49     cout<<sum+maxx<<endl;
50     return 0;
51 }

View Code

 

 

这个博客进行了时间上的优化：

https://www.cnblogs.com/mqxnongmin/p/10668455.html