Find maximum of minimum for every window size in a given array | An efficient C ++ program to find maximum of all minimums of windows of different sizes ; Used to find previous and next smaller ; Arrays to store previous and next smaller ; Initialize elements of left [ ] and right [ ] ; Fill elements of left [ ] using logic discussed on www . geeksforgeeks . org / next - greater - element / https : ; Empty the stack as stack is going to be used for right [ ] ; Fill elements of right [ ] using same logic ; Create and initialize answer array ; Fill answer array by comparing minimums of all lengths computed using left [ ] and right [ ] ; length of the interval ; arr [ i ] is a possible answer for this length ' len ' interval , check if arr [ i ] is more than max for ' len ' ; Some entries in ans [ ] may not be filled yet . Fill them by taking values from right side of ans [ ] ; Print the result ; Driver program
#include <iostream> NEW_LINE #include <stack> NEW_LINE using namespace std ; void printMaxOfMin ( int arr [ ] , int n ) { stack < int > s ; int left [ n + 1 ] ; int right [ n + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { left [ i ] = -1 ; right [ i ] = n ; } for ( int i = 0 ; i < n ; i ++ ) { while ( ! s . empty ( ) && arr [ s . top ( ) ] >= arr [ i ] ) s . pop ( ) ; if ( ! s . empty ( ) ) left [ i ] = s . top ( ) ; s . push ( i ) ; } while ( ! s . empty ( ) ) s . pop ( ) ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( ! s . empty ( ) && arr [ s . top ( ) ] >= arr [ i ] ) s . pop ( ) ; if ( ! s . empty ( ) ) right [ i ] = s . top ( ) ; s . push ( i ) ; } int ans [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) ans [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { int len = right [ i ] - left [ i ] - 1 ; ans [ len ] = max ( ans [ len ] , arr [ i ] ) ; } for ( int i = n - 1 ; i >= 1 ; i -- ) ans [ i ] = max ( ans [ i ] , ans [ i + 1 ] ) ; for ( int i = 1 ; i <= n ; i ++ ) cout << ans [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 10 , 20 , 30 , 50 , 10 , 70 , 30 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printMaxOfMin ( arr , n ) ; return 0 ; }