Sum of minimum and maximum elements of all subarrays of size k . | Python3 program to find Sum of all minimum and maximum elements Of Sub - array Size k . ; Returns Sum of min and max element of all subarrays of size k ; Initialize result ; The queue will store indexes of useful elements in every window In deque ' G ' we maintain decreasing order of values from front to rear In deque ' S ' we maintain increasing order of values from front to rear ; Process first window of size K ; Remove all previous greater elements that are useless . ; Remove from rear ; Remove all previous smaller that are elements are useless . ; Remove from rear ; Add current element at rear of both deque ; Process rest of the Array elements ; Element at the front of the deque ' G ' & ' S ' is the largest and smallest element of previous window respectively ; Remove all elements which are out of this window ; remove all previous greater element that are useless ; Remove from rear ; remove all previous smaller that are elements are useless ; Remove from rear ; Add current element at rear of both deque ; Sum of minimum and maximum element of last window ; Driver program to test above functions
from collections import deque NEW_LINE def SumOfKsubArray ( arr , n , k ) : NEW_LINE INDENT Sum = 0 NEW_LINE S = deque ( ) NEW_LINE G = deque ( ) NEW_LINE for i in range ( k ) : NEW_LINE INDENT while ( len ( S ) > 0 and arr [ S [ - 1 ] ] >= arr [ i ] ) : NEW_LINE INDENT S . pop ( ) NEW_LINE DEDENT while ( len ( G ) > 0 and arr [ G [ - 1 ] ] <= arr [ i ] ) : NEW_LINE INDENT G . pop ( ) NEW_LINE DEDENT G . append ( i ) NEW_LINE S . append ( i ) NEW_LINE DEDENT for i in range ( k , n ) : NEW_LINE INDENT Sum += arr [ S [ 0 ] ] + arr [ G [ 0 ] ] NEW_LINE while ( len ( S ) > 0 and S [ 0 ] <= i - k ) : NEW_LINE INDENT S . popleft ( ) NEW_LINE DEDENT while ( len ( G ) > 0 and G [ 0 ] <= i - k ) : NEW_LINE INDENT G . popleft ( ) NEW_LINE DEDENT while ( len ( S ) > 0 and arr [ S [ - 1 ] ] >= arr [ i ] ) : NEW_LINE INDENT S . pop ( ) NEW_LINE DEDENT while ( len ( G ) > 0 and arr [ G [ - 1 ] ] <= arr [ i ] ) : NEW_LINE INDENT G . pop ( ) NEW_LINE DEDENT G . append ( i ) NEW_LINE S . append ( i ) NEW_LINE DEDENT Sum += arr [ S [ 0 ] ] + arr [ G [ 0 ] ] NEW_LINE return Sum NEW_LINE DEDENT arr = [ 2 , 5 , - 1 , 7 , - 3 , - 1 , - 2 ] NEW_LINE n = len ( arr ) NEW_LINE k = 3 NEW_LINE print ( SumOfKsubArray ( arr , n , k ) ) NEW_LINE