Author |
Topic: Longest interval with maximum sum (Read 3942 times) |
|
Dufus
Newbie
Posts: 43
|
 |
Longest interval with maximum sum
« on: Aug 28th, 2009, 1:47am » |
 Quote  Modify
|
I recently stumbled upon this problem.
Find longest interval:-
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]
I have a solution which uses O(n) space and O(n.n) time. But can we do better?
I am very much tempted to use dynamic programming here but unable to find the optimal substructure.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #1 on: Aug 28th, 2009, 2:32am » |
Quote Modify
|
Make an array c[0..n-1] such that c[i]=a[i]-b[i]
Make an array d[0..n] such that d[i]=sumk=0..i-1 c[k]
Make an array e[-n..n] such that e[i] is the first index in d with sum i, or -1 if no such index exist.
From i=n..0, find the maximum i-e[d[i]] (excluding cases where e[d[i]]=-1)
Calling the i that maximizing this im, then p=e[d[im]], q=im-1.
Or something like that. (Might be off on a few details; concentrate on the broad idea.)
O(n) time and space.
|
| « Last Edit: Aug 28th, 2009, 2:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
GDD
Newbie
Gender: 
Posts: 2
|
|
Re: Longest interval with maximum sum
« Reply #2 on: Sep 25th, 2009, 4:26am » |
Quote Modify
|
Quite nervous as its my first post on this forum 
can't we use the same method which is used to find max sum subsequence..
A : 01000110001111001
B : 01100100010000000
Sum_a, Sum_b, start_index, end_index that keep track of best interval faced so far..
& similar parameters to keep track of current traversal.. csa, csb , si,ei
for first element ->
sum_a =0 csa=0
sum_b=0 csb=0
start_index=0 si=0
end_index=0 ei=0
for second element ->
sum_a =1 csa=1
sum_b=1 csb=1
start_index=0 si=0
end_index=1 ei=1
for third element ->
sum_a =1 csa=1
sum_b=1 csb=2
start_index=0 si=0
end_index=1 ei=2
.
.
.
for sixth element ->
sum_a =1 csa=2
sum_b=1 csb=3
start_index=0 si=0
end_index=1 ei=6
for seventh element ->
sum_a =3 csa=3
sum_b=3 csb=3
start_index=0 si=0
end_index=7 ei=7
so on..
waiting for expert comments
|
| « Last Edit: Sep 25th, 2009, 4:27am by GDD » |
IP Logged |
|
|
|
mistaken_id
Junior Member
Posts: 132
|
|
Re: Longest interval with maximum sum
« Reply #3 on: Sep 26th, 2009, 3:07pm » |
Quote Modify
|
If we can modify any of a or b arrays we can do it O(n) time and constant space
IF a[i] = b[i] then b[i] = 1
else b[i]=0
Now find max contiguous sum in b[i]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #4 on: Sep 27th, 2009, 8:08am » |
Quote Modify
|
on Sep 26th, 2009, 3:07pm, mistaken_id wrote:If we can modify any of a or b arrays we can do it O(n) time and constant space
IF a[i] = b[i] then b[i] = 1
else b[i]=0
Now find max contiguous sum in b[i] |
|
I don't see how that's going to work. You're throwing away information about when (the original) b[i] is greater or smaller than a[i]. And two opposite cases will cancel each other out.
if you have a=0101 and b=1100, then you want the answer p=1,q=4; not p=2,q=3; looking at a xor b = 0110 isn't going to give you the right answer.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #5 on: Sep 27th, 2009, 8:09am » |
Quote Modify
|
on Sep 25th, 2009, 4:26am, GDD wrote:| waiting for expert comments |
|
It's not really clear to me what you're doing. Can you explain your procedure?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Skandh
Junior Member
Gender:
Posts: 77
|
|
Re: Longest interval with maximum sum
« Reply #6 on: Sep 27th, 2009, 9:42am » |
Quote Modify
|
I was thinking something like this:
We have two arrays, A and B. Our objective is to get pair of intervals, one from A and second one from B.
We can get one interval very easily (in fact, it's trivial). It is (0,N-1). Since we are interested in longest interval, we can take (0,N-1) from the array which yields least sum of element between two arrays. Now search that sum in another array and get largest interval in that.
Illustration:
We have two arrays:
A : 01000110001111001
B : 01100100010000000
Sum of all elements of A=8
Sum of all elements of A=4
so from B we get interval (0,N-1). Now we only need to search largest interval in A which yields 4.
|
|
IP Logged |
I wanna pull by legs!!!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #7 on: Sep 27th, 2009, 10:57am » |
Quote Modify
|
The intervals have to be the same. You want to have  i=p..q a[i] = i=p..q b[i], with maximum q-p. So you can't take the interval (0, n-1) in one array, and something else in the other.
|
| « Last Edit: Sep 27th, 2009, 10:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Skandh
Junior Member
Gender:
Posts: 77
|
|
Re: Longest interval with maximum sum
« Reply #8 on: Sep 27th, 2009, 4:31pm » |
Quote Modify
|
on Sep 27th, 2009, 10:57am, towr wrote:| The intervals have to be the same. You want to have i=p..q a[i] = i=p..q b[i], with maximum q-p. So you can't take the interval (0, n-1) in one array, and something else in the other. |
|
Oh!!! I am sorry. I missed that part.
|
|
IP Logged |
I wanna pull by legs!!!
|
|
|
GDD
Newbie
Gender:
Posts: 2
|
|
Re: Longest interval with maximum sum
« Reply #9 on: Sep 28th, 2009, 9:09pm » |
Quote Modify
|
Trying to explain my solution (third post) in more detail....
A : 01000110001111001
B : 01100100010000000
Sum_a, Sum_b, start_index, end_index that keep track of best interval faced so far..
& similar parameters to keep track of current traversal.. csa, csb , si,ei
for first element ->
current -> csa=0 csb=0 si=0 ei=0
best interval so far -> sum_a =0 sum_b=0 start_index=0 end_index=0
for second element ->
current -> csa=1 csb=1 si=0 ei=1
modify :
best interval so far -> sum_a =1 sum_b=1 start_index=0 end_index=1
for third element ->
current -> csa=1 csb=2 si=0 ei=2
sum not equal dont modify :
best interval so far -> sum_a =1 sum_b=1 start_index=0 end_index=1
.
.
.
for sixth element ->
current -> csa=2 csb=3 si=0 ei=6
sum not equal dont modify :
best interval so far -> sum_a =1 sum_b=1 start_index=0 end_index=1
for seventh element ->
current -> csa=3 csb=3 si=0 ei=7
modify :
best interval so far -> sum_a =3 sum_b=3 start_index=0 end_index=7
.
.
.
for tenth element ->
current -> csa=3 csb=4 si=0 ei=10
sum not equal dont modify :
best interval so far -> sum_a =3 sum_b=3 start_index=0 end_index=7
for eleventh element ->
current -> csa=4 csb=4 si=0 ei=11
modify :
best interval so far -> sum_a =4 sum_b=4 start_index=0 end_index=11
.
.
.
for last element ->
current -> csa=8 csb=4 si=0 ei=17
sum not equal dont modify :
best interval so far -> sum_a =4 sum_b=4 start_index=0 end_index=11
Hence The required interval is from 0 to 11 (inclusive)
Hope now it makes some sense..
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Longest interval with maximum sum
« Reply #10 on: Sep 28th, 2009, 11:06pm » |
Quote Modify
|
Quote:| Hope now it makes some sense. |
|
What about start index ? It shows always 0 ,
But in the question , interval may start from any position to some other position in the array.
|
|
IP Logged |
|
|
|
jainshasha
Newbie
Posts: 14
|
|
Re: Longest interval with maximum sum
« Reply #11 on: Oct 5th, 2009, 12:20am » |
Quote Modify
|
i have a doubt ...
isnt every longest interval is going to start from the first element of the arrays
because array contains either 0 or 1 their is no negative element present in the array .
correct me if i m wrong.....
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #12 on: Oct 5th, 2009, 2:30am » |
Quote Modify
|
on Oct 5th, 2009, 12:20am, jainshasha wrote:i have a doubt ...
isnt every longest interval is going to start from the first element of the arrays |
|
No.
Try for example:
111001111 and 000100000
The underlined is the longest interval with shared maximum sum.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
game_iiith
Newbie
Posts: 5
|
|
Re: Longest interval with maximum sum
« Reply #13 on: Oct 8th, 2009, 1:20pm » |
Quote Modify
|
I have a DP approach to the problem ..
There is a recurrence in the problem i.e.
Suppose T[i,j] gives us the length of max sequence from index i to j in both arrays
T[i,j] = (j-i+1) if s1[i,j] = s2[i,j]
= max(T[i+1,j], T[i,j-1]) otherwise
I believe this works, if all agree then we shall figure out an intelligent way to implement this in O(n) space, which I belive is possible.
|
|
IP Logged |
|
|
|
hemanshu
Newbie
Gender:
Posts: 14
|
|
Re: Longest interval with maximum sum
« Reply #14 on: Oct 25th, 2009, 6:03am » |
Quote Modify
|
we can take 2 new different arrays let be c[] and d[] for arrays a and b.
then traversing in both arrays a and b.
put first element of both a and b in c and d respectively.
next tym put second element of both a and b in second position of c and d.... also add this second element to first elements of c and d.
so on as in third iteration put third element of both a and b in third position of c and d respectly and add this element to both first and second postions of c and d .
so on we can do and lasty we can compare if at any place values in c and d arrays are equal.
|
|
IP Logged |
|
|
|
alphare
Newbie
Posts: 8
|
|
Re: Longest interval with maximum sum
« Reply #15 on: Oct 26th, 2009, 2:23pm » |
Quote Modify
|
Use prefix sum:
(1) let array C=A-B (C[i]=A[i]-B[i])
(2) let array D, such that D[i]=sum(C[0..i])
(3) in D find the longest i-j such that D[i]=D[j] for any i>j.
(4) if (3) fails, just return the first A[i] such that D[i]==0, if there is no such i, return NULL.
|
|
IP Logged |
|
|
|
harish
Newbie
Gender:
Posts: 11
|
|
Re: Longest interval with maximum sum
« Reply #16 on: Oct 29th, 2009, 8:23am » |
Quote Modify
|
@towr
Can you explain your solution in detail..?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #17 on: Oct 29th, 2009, 9:00am » |
Quote Modify
|
on Oct 29th, 2009, 8:23am, harish wrote:@towr
Can you explain your solution in detail..? |
|
- As the problem is given, you want to find a range that gives the same sum in both arrays.
- The first step I take, subtracting array b from a, elementwise, reduces this to finding a range in array c that sums to 0.
- The second step, making a cumulative sum, further reduces the problem to finding two points in array d with the same value. A range [0..q] - [0..p-1] = [p..q], but now we don't have to sum all elements in between p and q.
- This would still take too much time to find, but because the total sum cannot exceed n, we can make a lookup table, array e. Now for each cumulative sum at index i, we can immediately find the earliest index j with the same value.
- So then we proceed to do that for each index i, and find the largest i-j we can.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
harish
Newbie
Gender:
Posts: 11
|
|
Re: Longest interval with maximum sum
« Reply #18 on: Oct 29th, 2009, 7:37pm » |
Quote Modify
|
thanks a lot towr. got it now. very good solution.
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Longest interval with maximum sum
« Reply #19 on: Oct 30th, 2009, 3:46am » |
Quote Modify
|
towr
Can your solution work in case of elements in array contains decimal number ?
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Longest interval with maximum sum
« Reply #20 on: Oct 30th, 2009, 4:04am » |
Quote Modify
|
Yes , It is working for all sets of nos
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #21 on: Oct 30th, 2009, 5:06am » |
Quote Modify
|
Actually, if the elements aren't 1s and 0s, then the last few steps (using array e) won't work as-is (because the sums are neither integers nor in a fixed range linear in n). But you could use a hash to get much the same run-time behaviour.
|
| « Last Edit: Oct 30th, 2009, 5:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Longest interval with maximum sum
« Reply #22 on: Mar 24th, 2010, 12:20am » |
Quote Modify
|
on Oct 29th, 2009, 9:00am, towr wrote:
- As the problem is given, you want to find a range that gives the same sum in both arrays.
- The first step I take, subtracting array b from a, elementwise, reduces this to finding a range in array c that sums to 0.
- The second step, making a cumulative sum, further reduces the problem to finding two points in array d with the same value. A range [0..q] - [0..p-1] = [p..q], but now we don't have to sum all elements in between p and q.
- This would still take too much time to find, but because the total sum cannot exceed n, we can make a lookup table, array e. Now for each cumulative sum at index i, we can immediately find the earliest index j with the same value.
- So then we proceed to do that for each index i, and find the largest i-j we can. |
|
Please check whether this can be reduced to "finding a maximum range in array c that sums to 0.".Wont that remove the max sum condition?if at an index both are 0's then such indexes will get added to the max range.
ex: for a = 100001101110 and b=010000101011 , as per my understanding ,answer should be 2nd underlined range where as towr's algo will give first underlined range. Am i right?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest interval with maximum sum
« Reply #23 on: Mar 24th, 2010, 2:53am » |
Quote Modify
|
on Mar 24th, 2010, 12:20am, kaka189 wrote:| Wont that remove the max sum condition? |
|
From the opening post I can only conclude that we want to find the longest interval.
Quote:| for a = 100001101110 and b = 010000101011 |
|
I'd think we'd get a = 100001101110 and b =010000101011
|
| « Last Edit: Mar 24th, 2010, 2:59am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Longest interval with maximum sum
« Reply #24 on: Mar 24th, 2010, 11:41am » |
Quote Modify
|
Quote:
- As the problem is given, you want to find a range that gives the same sum in both arrays.
- The first step I take, subtracting array b from a, elementwise, reduces this to finding a range in array c that sums to 0.
|
|
Towr, after first two steps, would this problem reduced find the Maximum subarray where number of zeros equal to number of ones (little modification in addition to zeros and 1's, we may have -1's).
But @KWillets solution for finding the Maximum subarry where number zeros equal to number of 1's
directly fits here.
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs; action=display;num=1268400913;start=25
Correct me If I am wrong.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print