@amir nice solution
On Sun, Dec 12, 2010 at 11:40 AM, Amir hossein Shahriari <
amir.hossein.shahri...@gmail.com> wrote:
> 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<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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
