title: Space-efficient algorithm for finding the largest balanced subarray?
body: <p>given an array of 0s and 1s, find maximum subarray such that number of zeros and 1s are equal.
  This needs to be done in O(n) time and O(1) space.</p>
  
  <p>I have an algo which does it in O(n) time and O(n) space. It uses a prefix sum array and exploits the fact that if the number of 0s and 1s are same then 
  sumOfSubarray = lengthOfSubarray/2 </p>
  
  <pre><code>#include&lt;iostream&gt;
  #define M 15
  
  using namespace std;
  
  void getSum(int arr[],int prefixsum[],int size) {
      int i;
      prefixsum[0]=arr[0]=0;
      prefixsum[1]=arr[1];
      for (i=2;i&lt;=size;i++) {
          prefixsum[i]=prefixsum[i-1]+arr[i];
      }
  }
  
  void find(int a[],int &amp;start,int &amp;end) {
      while(start &lt; end) {
          int mid = (start +end )/2;
          if((end-start+1) == 2 * (a[end] - a[start-1]))
                  break;
          if((end-start+1) &gt; 2 * (a[end] - a[start-1])) {
              if(a[start]==0 &amp;&amp; a[end]==1)
                      start++; else
                      end--;
          } else {
              if(a[start]==1 &amp;&amp; a[end]==0)
                      start++; else
                      end--;
          }
      }
  }
  
  int main() {
      int size,arr[M],ps[M],start=1,end,width;
      ;
      cin&gt;&gt;size;
      arr[0]=0;
      end=size;
      for (int i=1;i&lt;=size;i++)
              cin&gt;&gt;arr[i];
      getSum(arr,ps,size);
      find(ps,start,end);
      if(start!=end)
              cout&lt;&lt;(start-1)&lt;&lt;" "&lt;&lt;(end-1)&lt;&lt;endl; else cout&lt;&lt;"No soln\n";
      return 0;
  }
  </code></pre>