Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and back such that the sum of the
deficits of the two subarrays is greater than the deficit of the
entire array.
If you create an array containing the max leading deficit of the array
up to that point:
Deficit = MaxFromleft[0] = k – A[0];
BestLen = 0;
BestStart = 0;
For(I = 1; I < N; ++I)
{
Deficit += k – A[i];
MaxFromLeft[i] = max(Deficit, MaxFromLeft[i-1]);
if (Deficit < 0) BestLen = i+1;
}
Now Deficit is the deficit of the entire array, and MaxFromLeft[i] is
the largest deficit of a leading subarray including elements up to i.
Finally we can step across the array from the right computing the
deficit of the trailing subarray and then doing a binary search to
find the smallest leading subarray which gives a total deficit
reduction greater than the deficit of the entire array.
RightDeficit = MaxRightDeficit = 0;
for(j = N-1; j > BestLen; --j)
{
RightDeficit += k - A[j];
int min = 0;
int max = j - bestLen;
if (RightDeficit+MaxFromLeft[max] > Deficit)
{
while(max > min)
{
int mid = (min+max)/2;
if (RightDeficit+MaxFromLeft[mid] > deficit) max = mid;
else min = mid+1;
}
if ((j-max-1) > BestLen)
{
BestLen = j-max-1;
BestStart = max+1;
}
}
}
BestLen now is the length of the longest subarray averaging more than
k, and BestStart is the index of the first element in the input array
which is a part of that subarray. Note that there may be more than one
valid value of BestStart. This program just identifies one of them.
This algorithm is technically O(N*logN). However, testing on a wide
variety of data indicates that the inner loop usually executes about N
times or fewer.
Don
On Nov 20, 12:13 pm, Koup <anastasaki...@gmail.com> wrote:
> Consider an array of N integers. Find the longest contiguous subarray
> so that the average of its elements is greater than a given number k
>
> I know the general brute force solution in O(N^2). Is there any
> efficient solution using extra space?
--
