Trung bình cộng lớn nhất của mảng con II trong C++

Mô tả bài toán

Cho mảng n số nguyên, tìm mảng con liên tiếp có độ dài ≥ k sao cho giá trị trung bình cộng là lớn nhất. Trả về giá trị trung bình cộng lớn nhất đó.

Ví dụ: nums = [1,12,-5,-6,50,3], k = 4 → Đầu ra: 12.75 (mảng con [12,-5,-6,50] có độ dài 4, trung bình = 12.75).

Ý tưởng giải pháp (Tìm kiếm nhị phân + Kiểm tra khả thi)

Sử dụng tìm kiếm nhị phân trên giá trị trung bình x. Để kiểm tra xem có tồn tại mảng con độ dài ≥ k với trung bình ≥ x:

• Trừ x từ mọi phần tử → mảng arr[i] = nums[i] - x.
• Bài toán trở thành: tìm mảng con độ dài ≥ k có tổng ≥ 0.
• Dùng tổng tiền tố và duy trì tổng nhỏ nhất của tiền tố độ dài ≤ i-k để kiểm tra trong O(n).

Ví dụ minh họa

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

class Solution {
public:
    bool ok(double x, vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> arr(n);
        for (int i = 0; i < n; i++) arr[i] = nums[i] - x;
        double sum = 0, last = 0;
        for (int i = 0; i < k; i++) sum += arr[i];
        if (sum >= 0) return true;
        for (int i = 0, j = k; j < n; i++, j++) {
            last += arr[i];
            sum += arr[j];
            if (last < 0) {
                sum -= last;
                last = 0;
            }
            if (sum >= 0) return true;
        }
        return false;
    }

    double findMaxAverage(vector<int>& nums, int k) {
        double ret = 0, low = INT_MIN, high = INT_MAX;
        while (high - low > 1e-5) {
            double mid = low + (high - low) / 2;
            if (ok(mid, nums, k)) {
                low = mid;
                ret = mid;
            } else {
                high = mid;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 12, -5, -6, 50, 3};
    cout << ob.findMaxAverage(v, 4);
    return 0;
}

Đầu vào

{1,12,-5,-6,50,3}, 4

Đầu ra

12.75000