Maximum of all Subarrays of size k using set trong C++ STL

Trong hướng dẫn này, ta thảo luận chương trình tìm maximum của tất cả subarray kích thước k dùng set trong C++ STL.

Cho mảng kích thước N và số nguyên K. Nhiệm vụ: tìm phần tử lớn nhất trong mỗi cửa sổ K phần tử, cộng dồn và in ra.

Ví dụ

#include <bits/stdc++.h> using namespace std; int maxOfSubarrays(int arr[], int n, int k){    set<pair<int, int> > q;    set<pair<int, int> >::reverse_iterator it;    for (int i = 0; i < k; i++) q.insert({arr[i], i});    int sum = 0;    for (int j = 0; j < n - k + 1; j++) {       it = q.rbegin();       sum += it->first;       q.erase({arr[j], j});       q.insert({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; }

Đầu ra

182