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

Giả sử chúng ta có một mảng với n phần tử, chúng ta phải tìm mảng con liền nhau có độ dài k cho trước có giá trị trung bình lớn nhất. Chúng tôi phải trả về giá trị trung bình lớn nhất.

Vì vậy, nếu đầu vào là [1,13, -5, -8,48,3] và k =4, thì đầu ra sẽ là 12,0, như (13-5-8 + 48) / 4 =12,0.

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

• tổng:=0

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

  • sum:=sum + nums [i]

• maxi:=sum

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

  • sum:=sum + nums [i] - nums [i - k]

  • nếu sum> maxi, thì -

    • maxi:=sum

• trả về maxi / k

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   double findMaxAverage(vector<int>& nums, int k) {
      int sum = 0;
      for (int i = 0; i < k; i++) {
         sum += nums[i];
      }
      double maxi = sum;
      for (int i = k; i < nums.size(); i++) {
         sum += nums[i] - nums[i - k];
         if (sum > maxi) {
            maxi = sum;
         }
      }
      return maxi / k;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,13,-5,-8,48,3};
   cout << (ob.findMaxAverage(v, 4));
}

Đầu vào

{1,13,-5,-8,48,3}, 4

Đầu ra

12