【问题记录】——求序列子区间最大平均值

落日映苍穹つ 2022-09-01 14:45 121阅读 0赞

# 问题描述 #

给定一个序列求其长度大于f的子区间的平均值的最大值

## 思路 ##

求平均值可以用二分法来找平均值，先假设一个平均值，让原序列a减去假设平均值生成一个新序列b，b序列中有正有负，将b序列的前缀和存在sum数组中，区间\[i,j\]的和表示为sum\[j\]-sum\[i\]，如果存在区间和大于0，说明平均值还可以更大一些。这样求得的平均值稍有误差，可以控制误差的数量级。

## 实现代码 ##

int a[maxn];      //a数组
    double b[maxn];      //a数组减去假设平均值
    double sum[maxn];    //b的前缀和
    double judgeAve(int n, double mid, int f)
    { 
        for(int i = 1;i <= n;i++)
        { 
            b[i] = a[i] - mid;
            sum[i] = sum[i - 1] + b[i];
        }
        double min_val = 1e10, max_val = -1e10;
        for(int i = f;i <= n;i++)
        { 
            if(min_val > sum[i - f])
            { 
                min_val = sum[i - f];
            }
            if(max_val < sum[i]-min_val)
            { 
                max_val = sum[i]-min_val;
            }
        }
        return max_val;
    }
    double largestAve(int a[],int n,int f)//a数组，数组长度为n，f子区间长度
    { 
        double mid;
        double l = 0,r = 1e5, eps = 1e-8;
        while(r - l > eps)
        { 
            mid = (r + l) / 2;
            if(judgeAve(n, mid, f) > 0)
            { 
                l = mid;
            }
            else
            { 
                r = mid;
            }
        }
        return r;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关算法记录：最大子序列和

文章目录问题描述算法罗列一、O(N^2)，普通二、O(N logN)，分治法三、O(N)，联机算法 ---

ゝ一世哀愁。/ 2023年09月30日 13:45/ 0 赞/ 15 阅读

相关 Python乘积最大子序列问题

乘积最大子序列问题应用案例解法1 思路分析代码实现解法2 思路分析

淡淡的烟草味﹌/ 2023年07月04日 15:39/ 0 赞/ 16 阅读

相关【问题记录】——求序列子区间最大平均值

问题描述给定一个序列求其长度大于f的子区间的平均值的最大值思路求平均值可以用二分法来找平均值，先假设一个平均值，让原序列a减去假设平均值生成一个新序列b，b

落日映苍穹つ/ 2022年09月01日 14:45/ 0 赞/ 122 阅读

相关最大子序列之和问题

最大子序列之和问题这个问题非常有趣，因为有很多中算法可以解决这个问题。而这些算法的执行效率也多种多样。下面我们将看到四种算法，算法复杂度从指数一直过渡到线性复杂度。

清疚/ 2022年08月06日 06:06/ 0 赞/ 211 阅读

相关求最长公共子序列

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列

亦凉/ 2022年08月04日 04:26/ 0 赞/ 216 阅读

相关求最大连续子序列的和

给出一个序列，求出最大连续子序列的和，并输出最大连续子序列。如：\{-10, 1, 2, 3, 4, -5, -23, 100, 3, 7, -21\}，最大子序列是100

本是古典何须时尚/ 2022年05月31日 12:26/ 0 赞/ 244 阅读

相关 JS求最大子序列的和

这是一道笔试题，给定一个数组，求出这个数组中最大连续子序列的和。例如：在数组\[-2, 6, -1, 5, 4, -7, 2, 3\]中，和最大的子序列是\[6, -1, 5,

待我称王封你为后i/ 2022年05月09日 02:46/ 0 赞/ 218 阅读

相关经典算法-求最大子序列的和

最大连续子序列的和是一道很经典的算法问题，给定一个数列，其中可能有正数也可能有负数，我们的任务是找出其中连续的一个子数列（不允许空序列），使它们的和尽可能大。例：输入序列

偏执的太偏执、/ 2022年02月21日 10:59/ 0 赞/ 281 阅读

相关【面试】求数组子序列的最大和

一、问题描述输入一个整形数组，数组里可以有正数或负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)

深藏阁楼爱情的钟/ 2022年01月21日 00:17/ 0 赞/ 229 阅读

相关最大上升子序列，最大下降子序列，最大非增子序列，最大非减子序列

For example,\{1,5,2,4,3,5,6,4,7\}的最大上升子序列是\{1,2,3,5,6,7\}长度为6 现已知原序列a\[\]，如何求其最大上升子序列，最

雨点打透心脏的1/2处/ 2021年09月30日 02:00/ 0 赞/ 423 阅读