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 code
using System ; using System . Collections . Generic ; class Geeks { public static int SumOfKsubArray ( int [ ] arr , int k ) { int sum = 0 ; List < int > S = new List < int > ( ) ; List < int > G = new List < int > ( ) ; int i = 0 ; for ( i = 0 ; i < k ; i ++ ) { while ( S . Count != 0 && arr [ S [ S . Count - 1 ] ] >= arr [ i ] ) S . RemoveAt ( S . Count - 1 ) ; while ( G . Count != 0 && arr [ G [ G . Count - 1 ] ] <= arr [ i ] ) G . RemoveAt ( G . Count - 1 ) ; G . Add ( i ) ; S . Add ( i ) ; } for ( ; i < arr . Length ; i ++ ) { sum += arr [ S [ 0 ] ] + arr [ G [ 0 ] ] ; while ( S . Count != 0 && S [ 0 ] <= i - k ) S . RemoveAt ( 0 ) ; while ( G . Count != 0 && G [ 0 ] <= i - k ) G . RemoveAt ( 0 ) ; while ( S . Count != 0 && arr [ S [ S . Count - 1 ] ] >= arr [ i ] ) S . RemoveAt ( S . Count - 1 ) ; while ( G . Count != 0 && arr [ G [ G . Count - 1 ] ] <= arr [ i ] ) G . RemoveAt ( G . Count - 1 ) ; G . Add ( i ) ; S . Add ( i ) ; } sum += arr [ S [ 0 ] ] + arr [ G [ 0 ] ] ; return sum ; } public static void Main ( String [ ] args ) { int [ ] arr = { 2 , 5 , - 1 , 7 , - 3 , - 1 , - 2 } ; int k = 3 ; Console . WriteLine ( SumOfKsubArray ( arr , k ) ) ; } }