Sum of min and max of all subarrays of size k.

// C++ program to find sum of all minimum and maximum // elements Of Sub-array Size k. #include <bits/stdc++.h> using namespace std; // Returns sum of min and max element of all subarrays // of size k int SumOfKsubArray(int arr[], int N, int k) {  // To store final answer  int sum = 0;  // Find all subarray  for (int i = 0; i < N; i++) {  // To store length of subarray  int length = 0;  for (int j = i; j < N; j++) {  // Increment the length  length++;  // When there is subarray of size k  if (length == k) {  // To store maximum and minimum element  int maxi = INT_MIN;  int mini = INT_MAX;  for (int m = i; m <= j; m++) {  // Find maximum and minimum element  maxi = max(maxi, arr[m]);  mini = min(mini, arr[m]);  }  // Add maximum and minimum element in sum  sum += maxi + mini;  }  }  }  return sum; } // Driver program to test above functions int main() {  int arr[] = { 2, 5, -1, 7, -3, -1, -2 };  int N = sizeof(arr) / sizeof(arr[0]);  int k = 4;  cout << SumOfKsubArray(arr, N, k);  return 0; } 

// C++ program to find sum of all minimum and maximum // elements Of Sub-array Size k. #include <bits/stdc++.h> using namespace std; // Returns sum of min and max element of all subarrays // of size k int SumOfKsubArray(int arr[], int n, int k) {  int sum = 0; // to store our final sum  // multiset because nos. could be repeated  // multiset pair is {number,index}  multiset<pair<int, int> > ms;  int i = 0; // back pointer  int j = 0; // front pointer  while (j < n && i < n) {  ms.insert(  { arr[j], j }); // inserting {number,index}  // front pointer - back pointer + 1 is for checking  // window size  int windowSize = j - i + 1;  // Once they become equal, start what we need to do  if (windowSize == k) {  // extracting first since set is always in  // sorted ascending order  int mini = ms.begin()->first;  // extracting last element aka beginning from  // last (numbers extraction)  int maxi = ms.rbegin()->first;  // adding summation of maximum & minimum element  // of each subarray of k into final sum  sum += (maxi + mini);  // erasing the ith index element from set as it  // won't appaer in next window of size k  ms.erase({ arr[i], i });  // increasing back pointer for next window of  // size k;  i++;  }  j++; // always increments front pointer  }  return sum; } // Driver program to test above functions int main() {  int arr[] = { 2, 5, -1, 7, -3, -1, -2 };  int n = sizeof(arr) / sizeof(arr[0]);  int k = 4;  cout << SumOfKsubArray(arr, n, k);  return 0; } 

// C++ program to find sum of all minimum and maximum // elements Of Sub-array Size k. #include<bits/stdc++.h> using namespace std; // Returns sum of min and max element of all subarrays // of size k int SumOfKsubArray(int arr[] , int n , int k) {  int sum = 0; // 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  deque< int > S(k), G(k);  // Process first window of size K  int i = 0;  for (i = 0; i < k; i++)  {  // Remove all previous greater elements  // that are useless.  while ( (!S.empty()) && arr[S.back()] >= arr[i])  S.pop_back(); // Remove from rear  // Remove all previous smaller that are elements  // are useless.  while ( (!G.empty()) && arr[G.back()] <= arr[i])  G.pop_back(); // Remove from rear  // Add current element at rear of both deque  G.push_back(i);  S.push_back(i);  }  // Process rest of the Array elements  for ( ; i < n; i++ )  {  // Element at the front of the deque 'G' & 'S'  // is the largest and smallest  // element of previous window respectively  sum += arr[S.front()] + arr[G.front()];  // Remove all elements which are out of this  // window  if ( !S.empty() && S.front() == i - k)  S.pop_front();  if ( !G.empty() && G.front() == i - k)  G.pop_front();  // remove all previous greater element that are  // useless  while ( (!S.empty()) && arr[S.back()] >= arr[i])  S.pop_back(); // Remove from rear  // remove all previous smaller that are elements  // are useless  while ( (!G.empty()) && arr[G.back()] <= arr[i])  G.pop_back(); // Remove from rear  // Add current element at rear of both deque  G.push_back(i);  S.push_back(i);  }  // Sum of minimum and maximum element of last window  sum += arr[S.front()] + arr[G.front()];  return sum; } // Driver program to test above functions int main() {  int arr[] = {2, 5, -1, 7, -3, -1, -2} ;  int n = sizeof(arr)/sizeof(arr[0]);  int k = 4;  cout << SumOfKsubArray(arr, n, k) ;  return 0; }