Actually it is the problem #10 of chapter 8 of Programming Pearls 2nd edition. It asked two questions: given an array A[] of integers(positive and nonpositive), how can you find a continuous subarray of A[] whose sum is closest to 0? Or closest to a certain value t?
I can think of a way to solve the problem closest to 0. Calculate the prefix sum array S[], where S[i] = A[0]+A[1]+...+A[i]. And then sort this S according to the element value, along with its original index information kept, to find subarray sum closest to 0, just iterate the S array and do the diff of the two neighboring values and update the minimum absolute diff.
Question is, what is the best way so solve second problem? Closest to a certain value t? Can anyone give a code or at least an algorithm? (If anyone has better solution to closest to zero problem, answers are welcome too)
To solve this problem, you can build an interval-tree by your own, or balanced binary search tree, or even beneficial from STL map, in O(nlogn).
Following is use STL map, with lower_bound().
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
int A[] = {10,20,30,30,20,10,10,20};
// return (i, j) s.t. A[i] + ... + A[j] is nearest to value c
pair<int, int> nearest_to_c(int c, int n, int A[]) {
map<int, int> bst;
bst[0] = -1;
// barriers
bst[-int(1e9)] = -2;
bst[int(1e9)] = n;
int sum = 0, start, end, ret = c;
for (int i=0; i<n; ++i) {
sum += A[i];
// it->first >= sum-c, and with the minimal value in bst
map<int, int>::iterator it = bst.lower_bound(sum - c);
int tmp = -(sum - c - it->first);
if (tmp < ret) {
ret = tmp;
start = it->second + 1;
end = i;
}
--it;
// it->first < sum-c, and with the maximal value in bst
tmp = sum - c - it->first;
if (tmp < ret) {
ret = tmp;
start = it->second + 1;
end = i;
}
bst[sum] = i;
}
return make_pair(start, end);
}
// demo
int main() {
int c;
cin >> c;
pair<int, int> ans = nearest_to_c(c, 8, A);
cout << ans.first << ' ' << ans.second << endl;
return 0;
}