I have a sorted array of integers of size n. These values are not unique. What I need to do is : Given a B, I need to find an `i<A[n]`

such that the sum of `|A[j:1 to n]-i|`

is lesser than B and to that particular sum contribute the biggest number of A[j]s. I have some ideas but I can't seem to find anything better from the naive n*B and n*n algorithm. Any ideas about O(nlogn) or O(n) ? For example: Imagine

A[n] = 1 2 10 10 12 14 and B<7 then the best i is 12 cause I achieve having 4 A[j]s contribute to my sum. 10 and 11 are also equally good i's cause if i=10 I got 10 - 10 + 10 - 10 +12-10 + 14-10 = 6<7

These A[j]s must be contiguous. Because the problem is not trivial feel free to ask me if you find my descriptions ambiguous at some point

entirearray, but in your example you want the best contiguoussubarray. I assume your example is what you want. – Tony Huynh Nov 14 '12 at 0:17