@Amol +1 On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma <amolsharm...@gmail.com>wrote:
> 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. > -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT 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.
