home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum of all Subarrays of size k using set ใน C++ STL

คำอธิบาย

หาผลรวมของค่าสูงสุดในทุก subarray ขนาด k โดยใช้ set (balanced BST) เพื่อรักษาค่าสูงสุดของ sliding window

วิธีทำ

  1. ใช้ set<pair<int,int>> เก็บ {value, index} เรียงตาม value
  2. แทรก k ตัวแรก
  3. สไลด์ window: ลบตัวเก่าออก แทรกตัวใหม่เข้า
  4. ค่าสูงสุด = *set.rbegin() (iterator สุดท้าย)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int maxOfSubarrays(int arr[], int n, int k) {
    set<pair<int, int>> window;
    for(int i = 0; i < k; i++) {
        window.insert({arr[i], i});
    }
    
    int sum = 0;
    for(int i = 0; i <= n - k; i++) {
        sum += window.rbegin()->first; // max value
        window.erase({arr[i], i});
        if(i + k < n) window.insert({arr[i + k], i + 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