Re: [algogeeks] Longest interval with maximum sum
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;in;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.comwrote:
@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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.
Re: [algogeeks] Longest interval with maximum sum
@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;in;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.comwrote:
@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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.comalgogeeks%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.
Re: [algogeeks] Longest interval with maximum sum
@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.comwrote: @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.comalgogeeks%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.comalgogeeks%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.
Re: [algogeeks] Longest interval with maximum sum
@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.comalgogeeks%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.
Re: [algogeeks] Longest interval with maximum sum
@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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Longest interval with maximum sum
We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0... we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal... i.e. a[p]+a[p+1]+a[q]= b[p]+b[p+1]+b[[q]q -- 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.
