Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
It seems that what you really want to find is $i,j,k$ such that $i<A[n]$ and $\sum_{l=j}^k |A[l]-i| \leq B$ and $k-j$ is as large as possible. As it stands your description does not match your example. –  Tony Huynh Nov 13 '12 at 16:55
    
Why it does not? Can you explain? –  paramar Nov 13 '12 at 20:42
    
For your sum you are summing over the entire array, but in your example you want the best contiguous subarray. I assume your example is what you want. –  Tony Huynh Nov 14 '12 at 0:17
    
It is linear, actually. Just realize that if $a_k$ to $a_m$ is the answer, then $i$ is just the middle term. Now just move three markers left to right, spending constant time on the updates of a few relevant quantities. I'll post the algorithm when I have more time unless somebody else does it earlier :-). –  fedja Nov 15 '12 at 13:20
add comment

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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();
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.