Given an array containing only 0's and 1's, now we have to find the maximum subarray which contain equal no of 0's and 1's. Time complexity O(n).

/*
Logic for this program is taken from a post on geeksforgeeks.
I couldn't deduce an O(n) logic.
*/

#include<conio.h>

#include<iostream.h>

void main()

{

      clrscr();

      int array[]={1,0,0,1,0,1,1};

      int len = sizeof(array)/sizeof(int);

      int *sum = new int[len];

      sum[0]=((array[0]==0)?-1:1);

      int min=array[0],max=array[0];

      for(int i=1;i<len;i++)

      {

            sum[i]=sum[i-1]+((array[i]==0)?-1:1);

            if(sum[i]>max)

                  max=sum[i];

            if(sum[i]<min)

                  min=sum[i];

      }

      int *hash = new [max-min+1];

      int maxsize =-1,startindex;

      for( i=0;i<max-min+1;i++)

            hash[i]=-1;

      for(i=0;i<len;i++)

      {

            if(sum[i]==0)

            {

                  maxsize=i+1;

                  startindex=0;

            }

            if(hash[sum[i]-min]==-1)

                  hash[sum[i]-min]=i;

            else

            {

                  if((i-hash[sum[i]-min]) > maxsize)

                  {

                        maxsize=i-hash[sum[i]-min];

                        startindex = hash[sum[i]-min];

                  }

            }

      }

      cout<<"\n START : "<<startindex;

      cout<<"\n END   : "<<maxsize+startindex-1;

      getch();

}