C++의 최대 평균 부분배열 I

<시간/>

n개의 요소가 있는 배열이 있다고 가정하고 최대 평균값을 갖는 주어진 길이 k의 연속적인 하위 배열을 찾아야 합니다. 최대 평균값을 반환해야 합니다.

따라서 입력이 [1,13,-5,-8,48,3]이고 k =4인 경우 출력은 (13-5-8+48)/4 =12.0과 같이 12.0이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

합계 :=0
initialize i :=0의 경우, i
- 합계 :=합계 + 숫자[i]
최대치 :=합계
초기화 i :=k의 경우, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), −
- 합계 :=합계 + 숫자[i] - 숫자[i - k]
- 합계> 최대값이면 -
  - 최대치 :=합계
최대값/k를 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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));
}

입력

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