Рубрики

Максимум всех подмассивов размера k с использованием набора в C ++ STL

Для заданного массива размера N и целого числа K задача состоит в том, чтобы найти максимум для каждого смежного подмассива размера K и вывести сумму всех этих значений в конце.

Примеры:

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

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

Условие :

Подходить:
Set выполняет операцию вставки и удаления за время O (logK) и всегда сохраняет ключи в отсортированном порядке.
Идея состоит в том, чтобы использовать набор пар, где первый элемент в паре является самим элементом, а второй элемент в паре содержит индекс массива элемента.

  1. Выберите первые k элементов и создайте набор пар с этими элементами и их индексами, как описано выше.
  2. Теперь установите sum = 0 и используйте технику скользящего окна и Loop от j = 0 до n — k :
    • Получить максимальный элемент из набора (последний элемент) в текущем окне и обновить sum = sum + currMax .
    • Найдите самый левый элемент текущего окна в наборе и удалите его.
    • Вставьте следующий элемент текущего окна в набор, чтобы перейти к следующему окну.

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата суммы максимума
// все подмассивы размера k с использованием набора в C ++ STL

int maxOfSubarrays(int arr[], int n, int k)

{

    // Создать набор пар

    set<pair<int, int> > q;

  

    // Создать обратный итератор для набора

    set<pair<int, int> >::reverse_iterator it;

  

    // Вставляем первые k элементов вдоль

    // с их индексами в набор

    for (int i = 0; i < k; i++) {

        q.insert(pair<int, int>(arr[i], i));

    }

  

    // Для хранения суммы

    int sum = 0;

    for (int j = 0; j < n - k + 1; j++) {

  

        // Итератор до конца

        // устанавливается, так как имеет максимальное значение

        it = q.rbegin();

  

        // Добавить максимальный элемент

        // текущего окна

        sum += it->first;

  

        // Удалить arr [j] (крайний левый элемент

        // текущее окно) из набора

        q.erase(pair<int, int>(arr[j], j));

  

        // Вставить следующий элемент

        q.insert(pair<int, int>(arr[j + k], j + k));

    }

  

    // Возвращаем необходимую сумму

    return sum;

}

  
// Код драйвера

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

Сложность времени: O (n Log n)
Вспомогательное пространство: O (k)

Вышеуказанная проблема может быть решена за O (n) раз. Пожалуйста, смотрите ниже решение на основе Dequeue для того же.
Максимум скользящего окна (максимум всех подмассивов размера k)

Рекомендуемые посты:

Максимум всех подмассивов размера k с использованием набора в C ++ STL

0.00 (0%) 0 votes