fork(1) download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. int maxsubsum(int a[],int low, int high)
  6. {
  7.     int m,leftmss,rightmss;
  8.  
  9.     if(low==high)
  10.     {
  11.         return a[low];
  12.     }
  13.     else
  14.     {
  15.         m= (low+high)/2;
  16.         leftmss=maxsubsum(a,low,m);
  17.         rightmss=maxsubsum(a,m+1,high);
  18.     }
  19.     int leftsum=INT_MIN,rightsum=INT_MIN,sum=0;
  20.     for(int i=m+1; i<=high; i++)
  21.     {
  22.         sum+=a[i];
  23.         rightsum=max(rightsum,sum);
  24.     }
  25.     sum=0;
  26.     for(int i=m; i>=low; i--)
  27.     {
  28.         sum+=a[i];
  29.         leftsum=max(leftsum,sum);
  30.     }
  31.     int ans=max(leftmss,rightmss);
  32.     return max(ans,(leftsum+rightsum));
  33. }
  34.  
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(false);
  38.     int n;
  39.     cin>>n;
  40.     int a[n];
  41.     int b,counter=0;
  42.     for(int i=0; i<n; i++)
  43.     {
  44.         cin>>b;
  45.         if(b==0)
  46.         {
  47.             a[i]=1;
  48.         }
  49.         else
  50.         {
  51.             counter++;
  52.             a[i]=-1;
  53.         }
  54.     }
  55.     cout<<counter+maxsubsum(a,0,n-1);
  56. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
3
1 0 1
stdout
copy 
3
https://ideone.com/87RkJA
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!