C ++中的最大平均子数组II
假设我们有一个n个整数的数组，我们必须找到长度大于或等于k且具有最大平均值的连续子数组。我们必须找到最大平均值。
因此，如果输入类似于[1,12，-5，-6,50,3]，k=4，则输出将为12.75，如length为5时，最大值为10.8，length为6时，最大平均值为9.16667。因此输出为12.75。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数ok()，它将使用x，一个数组nums，k，
n：=nums的大小
定义大小为n的数组arr。
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
arr[i]：=nums[i]-x
sum：=0，last：=0
对于初始化i：=0，当i<k时，更新（将i增加1），执行-
sum：=sum+arr[i]
如果总和>=0，则-
返回真
对于初始化i：=0，j：=k，当j<n时，更新（i增加1），（j增加1），-
返回真
sum：=sum-最后
最后：=0
最后：=最后+arr[i]
sum：=sum+arr[j]
如果last<0，则-
如果总和>=0，则-
返回假
从主要方法中执行以下操作-
ret：=0，低：=-inf，高：=inf
当高-低>10^-5时
高：=中
低：=中
ret：=中
中：=低+（高-低）/2
如果ok(mid,nums,k)为真，则-
除此以外
返回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