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 <krishnai...@gmail.com> 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 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.
