@all plz.. tell if this thing would work..
assume 2 in place of every 0 in array. ie 1 1 0 0 0 1 0 1 be 1 1 2 2 2 1 2 1 then find max sub array wid sum length/2 * 3. this can be done in O(n) but worst case would still be O(n lgn) . On 1/26/12, Sanjay Rajpal <[email protected]> wrote: > +1 > * > Sanjay Kumar > B.Tech Final Year > Department of Computer Engineering > National Institute of Technology Kurukshetra > Kurukshetra - 136119 > Haryana, India > Contact: +91-8053566286 > * > > > > On Thu, Jan 26, 2012 at 6:28 PM, Ashish Goel <[email protected]> wrote: > >> replace all 0s by -1 >> keep additional array to get the sumHere at every position of all -1s and >> 1s. >> >> say you got >> 0 1 0 1 0 0 0 0 1 1 1 1 0 >> -1 1 -1 1 -1 -1 -1 -1 1 1 1 1 -1 >> sum -1 0 -1 0 -1 -2 -3 -4 -3 -2 -1 0 -1 >> >> all equal numbers in sum shows equal zeros and 1s between then including >> the end( between two -2 or two -3 or 0 0r -1) so biggest one can be >> figured >> out easily use a hash to store these cum sum, store their first and >> last occurrence, walk over to get max diff. >> >> >> >> >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> >> On Fri, Jan 27, 2012 at 1:48 AM, algoist <[email protected]> wrote: >> >>> Consider 2 temp arrays, B and C >>> >>> Where B gets updated for every find of 0 and C for every find of 1 >>> >>> i.e if(a[i]==0) >>> b[i]+=b[i-1]+1; >>> c[i]=c[i-1]; >>> i.e if(a[i]==1) >>> c[i]+=c[i-1]+1; >>> b[i]=b[i-1]; >>> >>> if(c[i]==b[i]) >>> update max. >>> >>> return max. >>> >>> This is O(N) algo. Is it right or i am missing anything here? >>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/YnKOgIEspAcJ. >>> >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
