given array- 1 0 0 1 1 1 0 1 0 1 for our convenience lets replace 0 by -1 array becomes 1 -1 -1 1 1 1 -1 1 -1 1
take another array count which which represents the sum till that index sum array becomes 1 0 -1 0 1 2 1 2 1 2 //count array now make an important observation that if a number repeats in the count array then between that two indexes equal number of zeros and ones have been added....... now take 2 arrays of size 2n+1 and index them from -n to n.....lets call them array a_front and a_back........the idea behind indexing is that the possible value of sum varies from -n(all 0's) to +n(all 1's) for *a_front* traverse the count array from front and for each number update index of it's first occurrence in the a_front array in this case...a_front[1]=0,a_front[0]=1,a_front[-1]=2,a_front[2]=6...only these four entries will be updated in the a_front array for *a_back* traverse the count array from back and for each number update index of it's last occurrence in the a_back array in this case...a_back[2]=9,a_back[1]=8,a_back[0]=3,a_back[-1]=2..only these four entries will be updated in the a_back array now traverse both a_front and a_back simultaneously max(a_back[i]-a_front[i]) will indicate the maximum subarray with equal zeros and ones. Hope this helps !! -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99> On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan <kartik.sac...@gmail.com>wrote: > Given a binary array ( array containing only 0s and 1s ). You have to > print the sub-array with > maximum number of equal 1s and 0s. > INPUT OUTPUT > 1001110101 0011101 > > > complex-O(n) > > -- > > *WITH REGARDS,* > * > * > *KARTIK SACHAN* > > *B.TECH 3rd YEAR* > *COMPUTER SCIENCE AND ENGINEERING* > *NIT ALLAHABAD* > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
