Sum of minimum and maximum elements of all subarrays of size k . | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int SumOfKsubArray ( int arr [ ] , int n , int k ) { int sum = 0 ; deque < int > S ( k ) , G ( k ) ; int i = 0 ; for ( i = 0 ; i < k ; i ++ ) { while ( ( ! S . empty ( ) ) && arr [ S . back ( ) ] >= arr [ i ] ) S . pop_back ( ) ; while ( ( ! G . empty ( ) ) && arr [ G . back ( ) ] <= arr [ i ] ) G . pop_back ( ) ; G . push_back ( i ) ; S . push_back ( i ) ; } for ( ; i < n ; i ++ ) { sum += arr [ S . front ( ) ] + arr [ G . front ( ) ] ; while ( ! S . empty ( ) && S . front ( ) <= i - k ) S . pop_front ( ) ; while ( ! G . empty ( ) && G . front ( ) <= i - k ) G . pop_front ( ) ; while ( ( ! S . empty ( ) ) && arr [ S . back ( ) ] >= arr [ i ] ) S . pop_back ( ) ; while ( ( ! G . empty ( ) ) && arr [ G . back ( ) ] <= arr [ i ] ) G . pop_back ( ) ; G . push_back ( i ) ; S . push_back ( i ) ; } sum += arr [ S . front ( ) ] + arr [ G . front ( ) ] ; return sum ; } int main ( ) { int arr [ ] = { 2 , 5 , -1 , 7 , -3 , -1 , -2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 3 ; cout << SumOfKsubArray ( arr , n , k ) ; return 0 ; }