MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Maximizing number of factors contributing in the sum of sorted array bounded by a value

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

-
 It seems that what you really want to find is $i,j,k$ such that $i ## 2 Answers 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.

-

This seems to work, but you'd better check for idiotic mistakes :).

import math;

srand(23);

int N=60;

int[] a;
for(int k=0;k<N;++k) a[k]=rand()%55;
a=sort(a);

int B=18;

a[N]=a[N-1]+B+1;

int K=0,k=0,m=0,s=0,S=0;

while(true)
{
while((k+m<N)&&(S<=B))
{
++m; S+=a[k+m]-a[s]; s+=m%2;
K=k;
}
if (k+m==N) {write(K,m-1); break;}
else {++k; ++s; S+=a[k+m]-a[s-1]-a[s-m%2]+a[k-1];}
}

write(a);
pause();

-