Kích thước mảng con lớn nhất sao cho mọi mảng con kích thước đó đều có tổng < k trong C++

Mô tả bài toán

Cho mảng arr[] kích thước N và số nguyên k. Tìm độ dài lớn nhất L sao cho mọi mảng con liên tiếp độ dài L đều có tổng ≤ k.

Giải pháp (Tìm kiếm nhị phân + Tổng tiền tố)

• Tính mảng tổng tiền tố prefixsum[i] = tổng arr[0..i-1].
• Tìm kiếm nhị phân độ dài mid từ 1 đến N:
  • Kiểm tra mọi mảng con độ dài mid: prefixsum[i] - prefixsum[i-mid] ≤ k ∀ i.
  • Nếu thỏa mãn → thử độ dài lớn hơn, ngược lại thử nhỏ hơn.
• Độ phức tạp: O(N log N).

Ví dụ minh họa

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

int bsearch(int prefixsum[], int n, int k) {
    int ans = -1, left = 1, right = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        int i;
        for (i = mid; i <= n; i++)
            if (prefixsum[i] - prefixsum[i - mid] > k) break;
        if (i == n + 1) { left = mid + 1; ans = mid; }
        else right = mid - 1;
    }
    return ans;
}

int maxSize(int arr[], int n, int k) {
    int prefixsum[n + 1];
    memset(prefixsum, 0, sizeof(prefixsum));
    for (int i = 0; i < n; i++) prefixsum[i + 1] = prefixsum[i] + arr[i];
    return bsearch(prefixsum, n, k);
}

int main() {
    int arr[] = {1, 2, 10, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 14;
    cout << maxSize(arr, n, k) << endl;
    return 0;
}

Đầu ra

2