Find Maximum of Minimums in Sliding Windows

Given an integer array of size n, find the maximum of the minimum’s for every window size in the array. Note that window size is 1..n.

Example:

When arr = [10, 20, 30, 50, 10, 70, 30], the output should be [70, 30, 20, 10, 10, 10, 10].

Explanation:

The first element in the output indicates the maximum of minimums of all windows of size 1.Minimums of windows of size 1 are [10, 20, 30, 50, 10, 70, 30]. The maximum is 70.

The second element in the output indicates the maximum of minimums of all windows of size 2. Minimums are now [10, 20, 30, 10, 10, 30]. The maximum is 30.

The third element in the output indicates the maximum of minimums of all windows of size 3. Minimums are now [10, 20, 10, 10, 10]. The maximum is 20.

Similarly, other elements of output are computed.

Contributed by Berkan Teber