Tìm tổng lớn nhất (hoặc nhỏ nhất) của mảng con kích thước k trong C++

Cho mảng arr[] và số k. Nhiệm vụ: Tìm tổng lớn nhất (hoặc nhỏ nhất) của mảng con kích thước k.

Ví dụ:

Đầu vào: arr[] = {55, 43, 12, 76, 89, 25, 99}, k = 2

Đầu ra: 165

Giải thích:

Mảng con kích thước 2 có tổng = 76 + 89 = 165

Phương pháp giải

Cách đơn giản: tìm tất cả mảng con kích thước k, trả về tổng lớn nhất.

Cách tối ưu (sliding window): Tính tổng mảng con đầu tiên. Với mảng con tiếp theo, trừ phần tử cũ, cộng phần tử mới. Cập nhật maxSum.

Chương trình minh họa

Ví dụ

#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;
}

Kết quả

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