Suppose we wish to find the subvector with the sum closest to zero
1. First calculate curr[i]=curr[i-1]+a[i];
2. Find the curr[u]-curr[l] which is 0 or close to 0
3. So from a[l+1] to a[u] is the subvector we want
Can be done nlogn, if you sort the array curr on the 2 step
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment