Sliding Window Maximum ( Maximum of all subarrays of size k ) | Python program to find the maximum for each and every contiguous subarray of size k ; A Deque ( Double ended queue ) based method for printing maximum element of all subarrays of size k ; Create a Double Ended Queue , Qi that will store indexes of array elements . The queue will store indexes of useful elements in every window and it will maintain decreasing order of values from front to rear in Qi , i . e . , arr [ Qi . front [ ] ] to arr [ Qi . rear ( ) ] are sorted in decreasing order ; Process first k ( or first window ) elements of array ; For every element , the previous smaller elements are useless so remove them from Qi ; Remove from rear ; Add new element at rear of queue ; Process rest of the elements , i . e . from arr [ k ] to arr [ n - 1 ] ; The element at the front of the queue is the largest element of previous window , so print it ; Remove the elements which are out of this window ; remove from front of deque ; Remove all elements smaller than the currently being added element ( Remove useless elements ) ; Add current element at the rear of Qi ; Print the maximum element of last window ; Driver code
from collections import deque NEW_LINE def printMax ( arr , n , k ) : NEW_LINE INDENT Qi = deque ( ) NEW_LINE for i in range ( k ) : NEW_LINE INDENT while Qi and arr [ i ] >= arr [ Qi [ - 1 ] ] : NEW_LINE INDENT Qi . pop ( ) NEW_LINE DEDENT Qi . append ( i ) ; NEW_LINE DEDENT for i in range ( k , n ) : NEW_LINE INDENT print ( str ( arr [ Qi [ 0 ] ] ) + " ▁ " , end = " " ) NEW_LINE while Qi and Qi [ 0 ] <= i - k : NEW_LINE INDENT Qi . popleft ( ) NEW_LINE DEDENT while Qi and arr [ i ] >= arr [ Qi [ - 1 ] ] : NEW_LINE INDENT Qi . pop ( ) NEW_LINE DEDENT Qi . append ( i ) NEW_LINE DEDENT print ( str ( arr [ Qi [ 0 ] ] ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 12 , 1 , 78 , 90 , 57 , 89 , 56 ] NEW_LINE k = 3 NEW_LINE printMax ( arr , len ( arr ) , k ) NEW_LINE DEDENT