b*****n
发帖数: 143 | 1 Problems 8.10 on page 85:
Find a subarray whose sum is closest to a
given value t.
I can only think of a brute-force method:
fist build the cumulation array, then scan
from first element to the last element. Each
scan is O(n). So the solution is O(n^2). I
wonder whether there is a better solution.
Thanks. | h***n
发帖数: 276 | 2 1) sort currsum array O(nlogn)
2) for each currsum[i], binary search the nearest number to currsum[i]+t (lo
gn) for each
to sum up O(nlogn)
【在 b*****n 的大作中提到】
: Problems 8.10 on page 85:
: Find a subarray whose sum is closest to a
: given value t.
: I can only think of a brute-force method:
: fist build the cumulation array, then scan
: from first element to the last element. Each
: scan is O(n). So the solution is O(n^2). I
: wonder whether there is a better solution.
: Thanks.
| b*****n
发帖数: 143 | 3 Thank you for your reply. But there is one problem in this solution:
Suppose when you search currsum[2]+t, the closest element is currsum[0],
then that means the sum of sub-array from 0 to 2 is -t, not t, right? | h***n
发帖数: 276 | 4 use another array to store currsum's indices to represent sorted currsum
in your case, currsum[2] would have a lower index than currsum[0]
【在 b*****n 的大作中提到】
: Thank you for your reply. But there is one problem in this solution:
: Suppose when you search currsum[2]+t, the closest element is currsum[0],
: then that means the sum of sub-array from 0 to 2 is -t, not t, right?
| v******y
发帖数: 22 | 5 The question is still intened to find a consecuritive sub array.
The solution is still one scan in O(n).
- maintain a sum of a FIFO sub array, one element out when sum > t. | s*******e
发帖数: 93 | 6 Does this still work if there can be negative numbers?
E.g. 1, -2, 3, -4, 5?
Could you please explain the FIFO sub array in more detail?
What I was thinking about is quite similar to hopen's idea
We can calculate the sum from a[0] to a[i] for each a[i]. (Say b[i]=a[0]+a[1
]+...+a[i])
In the meantime, maintain a BST to store the b[i] values
After getting b[i], we search if the node in the BST which is the most close
to t - b[i].
Then add b[i] to the BST (together with i).
It is nlogn, and one scan is enough.
【在 v******y 的大作中提到】
: The question is still intened to find a consecuritive sub array.
: The solution is still one scan in O(n).
: - maintain a sum of a FIFO sub array, one element out when sum > t.
| b*****n
发帖数: 143 | 7 Thank you for your replies, guys. So after the cumulation array is sorted,
we will ignore the original cum[0] and cum[1] during the binary search of
cum[2]+t. Is this the idea?
By the way, if my memory is correct, "Programming Pearls" claims that the
optimal solution to this kind of problem is nlog(n). So a linear-time
solution doesn't exist. (Note that we are looking for a subarray whose sum
is closest to t. So the sum could be either smaller or larger than t.)
Thanks again. | v******y
发帖数: 22 | 8 Oops, you are right, my former solution is not good if there's negative
values... now I could only come up with divide and concur method that is
O(n*log(n)*log(n))
Could anyone explain clearly an O(n*log(n)) solution? Thanks.
b[i]=a[0]+a[1
close
【在 s*******e 的大作中提到】
: Does this still work if there can be negative numbers?
: E.g. 1, -2, 3, -4, 5?
: Could you please explain the FIFO sub array in more detail?
: What I was thinking about is quite similar to hopen's idea
: We can calculate the sum from a[0] to a[i] for each a[i]. (Say b[i]=a[0]+a[1
: ]+...+a[i])
: In the meantime, maintain a BST to store the b[i] values
: After getting b[i], we search if the node in the BST which is the most close
: to t - b[i].
: Then add b[i] to the BST (together with i).
| b*m
发帖数: 6 | 9 for each cum[i], should search for cum[i]+/-t. so 2nlog(n) + original sort(n
(logn)) 3nLog(n) ==> nLog(n). | j*******a
发帖数: 61 | 10 Thanks for all posts. Just want to confirm I understand right, let me repeat
your ideas.
Assume input: 4, -1, 5, 2, 0, -2.
looks for the closest sub array for 3
0 1 2 3 4 5 get sums sort BS for 3
------------------------------------
0 | 4 3 8 10 10 8 n nlgn lgn
1 | -1 4 6 6 4 lgn lgn
2 | 5 7 7 5 lgn lgn
3 | 2 2 0 lgn lgn
4 | 0 -2 lgn lgn
5 | -2 lgn lgn
In this matrix,
Sum[0][j] is the cumulative sum.
Sum[1][j] is Sum[0][j]-a[0]. However, we don't need to compute all elements
in Sum[1][*]. Instead, we only need to compute the elements which is used in
binary search.
Sum[2][j] is Sum[1][j]-a[1]
...
For binary search, we need to keep the minimum of abs(diff). If we find an
element whose diff=sum-3=0, then it is what we want. If we did not find an
element whose diff=0, then we use the element whose abs(diff) is minimum.
sort: nlgn
binary search: nlgn
Total: nlgn
Correct me if I am wrong. Thanks. |
|
