Mảng con trung bình tối đa II trong C ++

Giả sử chúng ta có một mảng với n số nguyên, chúng ta phải tìm mảng con liền nhau có độ dài lớn hơn hoặc bằng k có giá trị trung bình lớn nhất. Chúng ta phải tìm giá trị trung bình lớn nhất.

Vì vậy, nếu đầu vào là [1,12, -5, -6,50,3], k =4, thì đầu ra sẽ là 12,75, như khi độ dài là 5, giá trị trung bình tối đa là 10,8, khi độ dài là 6 , giá trị trung bình lớn nhất là 9.16667. Do đó, sản lượng là 12,75.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm ok (), điều này sẽ nhận x, một số mảng, k,

• n:=kích thước của nums

• Xác định arr mảng có kích thước:n.

• để khởi tạo i:=0, khi i

  • arr [i]:=nums [i] - x

• sum:=0, last:=0

• để khởi tạo i:=0, khi i

  • sum:=sum + arr [i]

• nếu sum> =0, thì -

  • trả về true

• để khởi tạo i:=0, j:=k, khi j

  • cuối cùng:=last + arr [i]

  • sum:=sum + arr [j]

  • nếu cuối cùng <0, thì -

    • sum:=sum - last

    • cuối cùng:=0

  • nếu sum> =0, thì -

    • trả về true

• trả về false

• Từ phương thức chính, hãy làm như sau -

• ret:=0, low:=-inf, high:=inf

• trong khi cao - thấp> 10 ^ -5, thực hiện

  • giữa:=low + (cao - thấp) / 2

  • nếu ok (mid, nums, k) là true, thì -

    • thấp:=trung bình

    • ret:=mid

  • Nếu không

    • cao:=giữa

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,12,-5,-6,50,3};
   cout << (ob.findMaxAverage(v, 4));
}

Đầu vào

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

Đầu ra

12.75000