หาผลรวมสูงสุด (หรือต่ำสุด) ของซับอาร์เรย์ขนาด k ใน C++

โจทย์

ได้รับอาร์เรย์ arr[] และจำนวน k ทางเราต้อง หาผลรวมสูงสุด (หรือต่ำสุด) ของซับอาร์เรย์ที่มีขนาด k

ตัวอย่าง

Input: arr[] = {55, 43, 12, 76, 89, 25, 99}, k = 2

Output: 165

อธิบาย: ซับอาร์เรย์ขนาด 2 ที่มีผลรวมมากที่สุดคือ 76 + 89 = 165

แนวทางแก้ปัญหา

วิธีแบบง่าย: หาผลรวมของทุกซับอาร์เรย์ขนาด k แล้วเลือกค่าสูงสุด

วิธี Sliding Window (มีประสิทธิภาพกว่า):

1. คำนวณผลรวมของ k ตัวแรก
2. เลื่อนหน้าต่าง: ลบตัวแรกออก บวกตัวใหม่เข้า
3. อัปเดตค่าสูงสุดในแต่ละขั้นตอน

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

int findMaxSumSubarray(int arr[], int n, int k) {
    if (n < k) { cout << "Invalid"; return -1; }
    int maxSum = 0;
    for (int i = 0; i < k; i++) maxSum += arr[i];
    int curr_sum = maxSum;
    for (int i = k; i < n; i++) {
        curr_sum += arr[i] - arr[i - k];
        maxSum = max(maxSum, curr_sum);
    }
    return maxSum;
}

int main() {
    int arr[] = {55, 43, 12, 76, 89, 25, 99};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "The sum of subarray with max sum of size " << k << " is " << findMaxSumSubarray(arr, n, k);
    return 0;
}

ผลลัพธ์

The sum of subarray with max sum of size 2 is 165