each value in A and B is 0 or 1 so the sum of all elements in A (or B) is n
so the sum of all elements in C which is the sum of differences between
values in A and B is between -n and n
now we want to maximize j-i for which C[i]+C[i+1]+...+C[j] = 0
suppose that sum(i) = C[1]+C[2]+...+C[i] which is sum of first i elements in
C
if sum(i)==sum(j) this means that C[i]+C[i+1]+...C[j] = 0
and we know that -n<=sum(i)<=n
so we can build another array aux which aux[k] is -1 if there was not any i
for which sum(i)=k or aux[k]=first i for which sum(i)=k
here's a sample code for the rest:
sum=0;
aux[0]=0;
for (i=0;i<n;i++){
sum+=C[i];
if (aux[sum]==-1)
aux[sum]=i+1;
else
result=max(result,i+1-aux[sum]);
}
return result;
On Sat, Dec 11, 2010 at 3:30 PM, ADITYA KUMAR <aditya...@gmail.com> wrote:
>
> @amir can u explain a bit more...
>
> On Tue, Dec 7, 2010 at 10:09 PM, Amir hossein Shahriari <
> amir.hossein.shahri...@gmail.com> wrote:
>
>> @jai : since sum of all values in C is between -n and n the last step can
>> be done in O(n) time and O(n) space
>>
>>
>> On Sun, Dec 5, 2010 at 12:44 PM, jai gupta <sayhelloto...@gmail.com>wrote:
>>
>>> @fenghuang: the last step will take O(n logn ) . Or there is some better
>>> way?
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards
> Aditya Kumar
> B-tech 3rd year
> Computer Science & Engg.
> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
