Codeforces 327A. Flipping Game Solution

 Algorithm

1. Consider all subarrays and find a subarray with maximum value of (count of 1s) – (count of 0s)

2. Considers this value be maxDiff. Finally return count of zeros in original array + maxDiff.

  Solution in C++:

 ///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

1. #include<bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.  
6. int n,a[109],i,j,zero=0,one=0,one1=0,mxcnt=0;
7. cin>>n;
8. for(i=0; i<n; i++)
9. {
10. cin>>a[i];
11. if(a[i]==1)
12. one1++;
13. }
14. if(n==1&&a[0]==1)
15. {
16. cout<<"0"<<endl;
17. return 0;
18. }
19. else if(one1==n)
20. {
21. cout<<n-1<<endl;
22. return 0;
23. }
24. for(i=0; i<n; i++)
25. {
26. zero=0;
27. one=0;
28. for(j=i; j<n; j++)
29. {
30. (a[j]==0)?zero++:one++;
31. mxcnt=max(mxcnt,zero-one);
32. }
33. }
34. cout<<one1+mxcnt<<endl;
35. }