C++での最大平均サブアレイII

n個の整数を持つ配列があるとすると、最大平均値を持つk以上の長さの連続するサブ配列を見つける必要があります。最大平均値を見つける必要があります。

したがって、入力が[1,12、-5、-6,50,3]、k =4の場合、長さが5の場合のように、出力は12.75になります。長さが6の場合、最大平均値は10.8です。 、最大平均値は9.16667です。したがって、出力は12.75です。

これを解決するには、次の手順に従います-

• 関数ok（）を定義します。これには、x、配列nums、k、

  が必要です。

• n：=numsのサイズ

• サイズの配列arrを定義します：n。

• 初期化i：=0の場合、i

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

• 合計：=0、最後：=0

• 初期化i：=0の場合、i

  • 合計：=合計+ arr [i]

• 合計>=0の場合、-

  • trueを返す

• 初期化i：=0、j：=kの場合、j

  • last：=last + arr [i]

  • 合計：=合計+ arr [j]

  • 最後の<0の場合、-

    • 合計：=合計-最後

    • 最後：=0

  • 合計>=0の場合、-

    • trueを返す

• falseを返す

• メインの方法から、次のようにします-

• ret：=0、low：=-inf、high：=inf

• 高-低>10^ -5、実行

  • 中：=低+（高-低）/ 2

  • ok（mid、nums、k）が真の場合、-

    • 低：=中

    • ret：=mid

  • それ以外の場合

    • 高：=中

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

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

入力

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

出力

12.75000