Máximo de todos los Subarrays de tamaño k usando set en C++ STL

Dada una array de tamaño N y un número entero K , la tarea es encontrar el máximo para todos y cada uno de los subconjuntos contiguos de tamaño K e imprimir la suma de todos estos valores al final.

Ejemplos:

Entrada: arr[] = {4, 10, 54, 11, 8, 7, 9}, K = 3
Salida: 182

Entrada: arr[] = {1, 2, 3, 4, 1, 6, 7, 8, 2, 1}, K = 4
Salida: 45

requisito previo :

• Técnica de ventana corrediza
• Establecer en C++ STL

Enfoque:
el conjunto realiza la operación de inserción y extracción en tiempo O (logK) y siempre almacena las claves en el orden ordenado.
La idea es utilizar un conjunto de pares donde el primer elemento del par es el propio elemento y el segundo elemento del par contiene el índice de array del elemento.

1. Elija los primeros k elementos y cree un conjunto de pares con estos elementos y su índice como se describe arriba.
2. Ahora, establezca sum = 0 y use la técnica de deslizamiento de ventana y Loop from j = 0 to n – k :
   • Obtenga el elemento máximo del conjunto (el último elemento) en la ventana actual y actualice sum = sum + currMax .
   • Busque el elemento más a la izquierda de la ventana actual en el conjunto y elimínelo.
   • Inserte el siguiente elemento de la ventana actual en el conjunto para pasar a la siguiente ventana.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the sum of maximum of
// all k size sub-arrays using set in C++ STL
int maxOfSubarrays(int arr[], int n, int k)
{
    // Create a set of pairs
    set<pair<int, int> > q;
  
    // Create a reverse iterator to the set
    set<pair<int, int> >::reverse_iterator it;
  
    // Insert the first k elements along
    // with their indices into the set
    for (int i = 0; i < k; i++) {
        q.insert(pair<int, int>(arr[i], i));
    }
  
    // To store the sum
    int sum = 0;
    for (int j = 0; j < n - k + 1; j++) {
  
        // Iterator to the end of the
        // set since it has the maximum value
        it = q.rbegin();
  
        // Add the maximum element
        // of the current window
        sum += it->first;
  
        // Delete arr[j] (Leftmost element of
        // current window) from the set
        q.erase(pair<int, int>(arr[j], j));
  
        // Insert next element
        q.insert(pair<int, int>(arr[j + k], j + k));
    }
  
    // Return the required sum
    return sum;
}
  
// Driver Code
int main()
{
    int arr[] = { 4, 10, 54, 11, 8, 7, 9 };
  
    int K = 3;
  
    int n = sizeof(arr) / sizeof(arr[0]);
  
    cout << maxOfSubarrays(arr, n, K);
  
    return 0;
}

182

Complejidad de Tiempo : O(n Log n)
Espacio Auxiliar : O(k)

El problema anterior se puede resolver en tiempo O(n). Consulte a continuación la solución basada en Dequeue para lo mismo.
Máximo de ventana deslizante (Máximo de todos los subarreglos de tamaño k)