首页 > 编程语言 > 详细

最大平均值子数组

时间:2017-06-20 17:05:11      阅读:942      评论:0      收藏:0      [点我收藏+]

LintCode

给出一个整数数组,有正有负。找到这样一个子数组,他的长度大于等于 k,且平均值最大。

 

二分平均值,平均值的上限r是单个最大值,下限l是所有数的和.

mid=(l+r)/2

设sum[i]=nums[0]+nums[1]+nums[2]...nums[i]-i*mid;

保存m=min(sum[0],sum[1],sum[2]...sum[i-k+1].

如果发现sum[i]>m,说明在num[i-k+1]到num[i]之间的数,平均值大于mid.所以sum才能上涨.

class Solution {
public:
    double search(vector<int>&nums, int k, double mid) {
        vector<double> sum(nums.size() + 1);
        double min = 0;
        for (int i = 1; i <= nums.size(); i++) {
            sum[i] = sum[i - 1] + (double)nums[i - 1] - mid;
            if (i >= k && sum[i] >= min)
                return true;
            if (i >= k)
                min = ::min(min, sum[i - k + 1]);
        }
        return false;
    }
    double maxAverage(vector<int>& nums, int k) {
        vector<int> sum(nums.size());
        sum[0] = nums[0];
        for (int i = 1; i < nums.size(); i++)
            sum[i] = sum[i - 1] + nums[i];
        double l = (double)sum.back() / nums.size(), r = *max_element(nums.begin(), nums.end());
        while (r - l > 1e-6) {
            double mid = (l + r) / 2.0;
            if (search(nums, k, mid))
                l = mid;
            else
                r = mid;
        }
        return r;
    }
};

 

 

最大平均值子数组

原文:http://www.cnblogs.com/yujinding/p/7054757.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!