Tổng lớn nhất mảng con có ít nhất K phần tử C++

Cho mảng a và số k. Tìm tổng lớn nhất của mảng con liên tục có độ dài ít nhất k.

Thuật toán (Kadane biến thể + Prefix Max)

• Tính maxEndingHere[i] = max subarray sum kết thúc tại i (Kadane chuẩn).
• Tính tổng k phần tử đầu: sum.
• Duyệt i = k .. n-1:
  • sum += a[i] - a[i-k] (cửa sổ trượt kích thước k).
  • ans = max(ans, sum) (chính xác k phần tử).
  • ans = max(ans, sum + maxEndingHere[i-k]) (mở rộng về trái).

Triển khai C++

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

int maxSubarrayAtLeastK(int a[], int n, int k) {
    vector maxEnd(n);
    maxEnd[0] = a[0];
    for (int i = 1; i < n; i++)
        maxEnd[i] = max(a[i], maxEnd[i-1] + a[i]);

    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int ans = sum;

    for (int i = k; i < n; i++) {
        sum += a[i] - a[i-k];
        ans = max(ans, sum);
        ans = max(ans, sum + maxEnd[i-k]);
    }
    return ans;
}

int main() {
    int a[] = {5, 3, 7, -5, 6, 2, 1};
    cout << maxSubarrayAtLeastK(a, 7, 6) << endl; // 19
    return 0;
}

Kết quả

19