artgb - 3 years ago 189

C++ Question

I had an algorithm problem asking to get

`max(min(A[i .. i+d]))`

`O (n)`

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)`

`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)

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**