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



Maximizing number of factors contributing in the sum of sorted array bounded by a value
It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}\_t$ and $\mathbf{Y}\_t$ which are respectively the best valid sequence with indices in $\{1, \dots, t\}$ and the best valid sequence which ends with $A[t]$. At time $t+1$ we update $\mathbf{X}\_t$ and $\mathbf{Y}\_t$ as follows. If $(\mathbf{Y}\_t, A[t+1])$ is a valid sequence of length longer than $\mathbf{X}\_t$, then we set 


$\mathbf{X}\_{t+1}:=(\mathbf{Y}\_t, A[t+1])$ and $\mathbf{Y}\_{t+1}:=(\mathbf{Y}\_t, A[t+1])$.


Otherwise, we set $\mathbf{X}\_{t+1}:=\mathbf{X}\_t$ and we can compute $\mathbf{Y}\_{t+1}$ in $O(\log (n))$-time via binary search. 


