Sum of minimum and maximum elements of all subarrays of size k . | Java 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
import java . util . Deque ; import java . util . LinkedList ; public class Geeks { public static int SumOfKsubArray ( int arr [ ] , int k ) { int sum = 0 ; Deque < Integer > S = new LinkedList < > ( ) , G = new LinkedList < > ( ) ; int i = 0 ; for ( i = 0 ; i < k ; i ++ ) { while ( ! S . isEmpty ( ) && arr [ S . peekLast ( ) ] >= arr [ i ] ) S . removeLast ( ) ; while ( ! G . isEmpty ( ) && arr [ G . peekLast ( ) ] <= arr [ i ] ) G . removeLast ( ) ; G . addLast ( i ) ; S . addLast ( i ) ; } for ( ; i < arr . length ; i ++ ) { sum += arr [ S . peekFirst ( ) ] + arr [ G . peekFirst ( ) ] ; while ( ! S . isEmpty ( ) && S . peekFirst ( ) <= i - k ) S . removeFirst ( ) ; while ( ! G . isEmpty ( ) && G . peekFirst ( ) <= i - k ) G . removeFirst ( ) ; while ( ! S . isEmpty ( ) && arr [ S . peekLast ( ) ] >= arr [ i ] ) S . removeLast ( ) ; while ( ! G . isEmpty ( ) && arr [ G . peekLast ( ) ] <= arr [ i ] ) G . removeLast ( ) ; G . addLast ( i ) ; S . addLast ( i ) ; } sum += arr [ S . peekFirst ( ) ] + arr [ G . peekFirst ( ) ] ; return sum ; } public static void main ( String args [ ] ) { int arr [ ] = { 2 , 5 , - 1 , 7 , - 3 , - 1 , - 2 } ; int k = 3 ; System . out . println ( SumOfKsubArray ( arr , k ) ) ; } }