Algorithm to compute maximum of blocks

Question

We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total).

One algorithm is to compute the maximum of every $n/2$ consecutive numbers separately. This leads to an $O(n^2)$ algorithm.

Can we do better? Perhaps using a heap or an appropriate data structure?

Answer 1

Here some ideas:

Put the numbers in an array and repeat it. This allows to view the problem in a different light. Now you just have to compute a bunch of range maximum queries. RMQ is a well studied topic, and there are countless efficient solutions:

• Sqrt-Decomposition: $O(N)$ preprocessing, $O(\sqrt{N})$ per query.
• Segment Tree: $O(N)$ preprocessing, $O(\log N)$ per query.
• Sparse-Tables: $O(N \log N)$ preprocessing, $O(1)$ per query
• Farach-Colton and Bender: $O(N)$ preprocessing, $O(1)$ per query
• and many more

Most of them are of a more general nature, e.g. they allow modifying the array. And some (like Farach-Colton and Bender) are not very pleasant to implement. This is probably way too much for your application.

So here I want to present a very simple and short data structure, which is still capable to compute the maxima in optimal $O(n)$ time: the Max-Queue.

A Max-Queue is a queue, that functions like a normal queue (you can insert values at one end and remove values at the other), and also can compute the maximal value in $O(1)$ time. CP-algorithms.com describes a few possible implementations of min-queues, which are just the dual data structure. I'll use method 2 here:

The queue internally keeps track of how many items we have pushed and popped already, and stores the elements as pairs (value, push_index). E.g. pushing the elements [1, 6, 2, 4, 3] leads to the queue: [(1,0), (6,1), (2,2), (4,3), (3,4)]. And one thing more. It will do this in such a way, so that we only store elements in a monotone decreasing way, so that it stores the maximum at the beginning, and so that after popping the maximum the next maximum is still at the beginning. This would give us the queue structure: [(6,1), (4,3), (3,4)]. This allows looking at the maximum in $O(1)$ time (just look at the first element), inserting in amortized $O(1)$ time (you need to delete all elements from the back that are smaller than the new value), and popping in $O(1)$.

A Min-Queue implementation can be found under the link above. Each method consists of only 1-4 lines of code.

With the Max-Queue we can find all desired maxima in $O(n)$ time. We insert the first $n/2$ numbers in the queue, and print the maximum. The pop a value, insert the next one, and print the maximum. Repeat until you printed $n$ values.

Answer 2

This is a variation of a problem called sliding window maximum. A linear time solution to the sliding window maximum problem is given there: https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/

In your case the window size is $n/2$ and the sequence is simply the concatenation of two copies of your original sequence.

Answer 3

First, try to solve it for a line.

Here's a hint. Think about what happens when you know the value for a "window" $s_i = \sum \{i, i+1, ..., i+n/2\}$ and "slide" it one step to the right.

What will the sum be for $s_{i+1} = \sum\{i+1, i+2, ..., i+1+n/2\}$ relative to $s_i$?