C++-এ সর্বোচ্চ গড় সাবঅ্যারে II

একটি n পূর্ণসংখ্যার অ্যারে দেওয়া আছে। আমাদের এমন একটি সংলগ্ন সাবঅ্যারে খুঁজে বের করতে হবে যার দৈর্ঘ্য k-র চেয়ে বড় বা সমান এবং যার গড় মান সর্বোচ্চ। সেই সর্বোচ্চ গড় মান রিটার্ন করতে হবে।

ইনপুট [1,12,-5,-6,50,3], k=4 হলে আউটপুট 12.75। কারণ দৈর্ঘ্য ৫-এ সর্বোচ্চ গড় ১০.৮, দৈর্ঘ্য ৬-এ ৯.১৬৬৬৭।

সমাধানের ধাপসমূহ

• ok() ফাংশন সংজ্ঞায়িত করুন যা x, nums, k নেয়
• n := nums-র আকার
• arr অ্যারে (আকার n) তৈরি করুন
• প্রতিটি i-এর জন্য arr[i] := nums[i] - x
• sum := 0, last := 0
• প্রথম k উপাদানের যোগফল sum-এ করুন
• যদি sum >= 0 হয়, true রিটার্ন করুন
• i:=0, j:=k থেকে শুরু করে j
• last += arr[i]
• sum += arr[j]
• যদি last < 0 হয়, sum := sum - last, last := 0
• যদি sum >= 0 হয়, true রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool ok(double x, vector <int>& nums, int k){
        int n = nums.size();
        double arr[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nums[i] - x;
        }
        double sum = 0;
        double 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;
        double low = INT_MIN;
        double 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));
}

ইনপুট

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

আউটপুট

12.75000