artgb artgb - 1 year ago 104
C++ Question

calculating max(min(A[i .. i+d])) in O(n) time O(n) memory

I had an algorithm problem asking to get

max(min(A[i .. i+d]))
in
O (n)
time.

General Solution:

int max = 0;
for( i = 0; i< n-d; i++){
int min = MX;
for( j = i; j < i + d; j++)
if(min > A[j])
min = A[j];
if(max < min)
max = min;
}
printf("%d\n", max);


But it will take O(n x d) not O(n)

Better Solution: using Range_minimum_query

int max = 0;
for( i = 0; i< n-d; i++){
int min = RMQ( i , i + d);
if(max < min)
max = min;
}
printf("%d\n", max);


It will take
O(log(d) * n)
as RMQ's average time is
log(d)


I thought this problem in my head about 15 days, but not renovation yet.
Could anyone solve this problem efficiently?

i/o data:
1<n<10^7 1<d<n


input : n = 10, d = 3, A[i] > 0
1, 3, 2, 4, 5, 6, 7, 8, 9, 10
result : 8 //= max(1, 2, 2, 4, 5, 6, 7, 8)

Answer Source

Following the Range minimum query philosophy (which is good for random access), I would use a Double-ended queue (which is good for sequential access), which offers a average complexity of O(1) for all operations*.

*except insertion/deletion)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download