2023年华为OD机考真题：几何平均值最大子数组

算法刷题2年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：几何平均值最大子数组
知识点数组二分查找
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大子数组，并输出其位置和大小。（K个数的几何平均值为K个数的乘积的K次方根）
若有多个子数组的几何平均值均为最大值，则输出长度最小的子数组。
若有多个长度相同的子数组的几何平均值均为最大值，则输出最前面的子数组。
输入描述：
第一行输入为N、L，N表示numbers的大小（1 <= N <= 100000），L表示子数组的最小长度（1 <= L <= N），
之后N行表示numbers中的N个数，每个一行（10-9 <= numbers[i] <= 109）。
输出描述：
输出子数组的位置（从0开始计数）和大小，中间用一个空格隔开。
补充说明：
用例保证除几何平均值为最大值的子数组外，其他子数组的几何平均值至少比最大值小最大值的10-10倍
示例1
输入：
3 2
2
2
3
输出：
1 2
说明：
长度至少为2的子数组共三个，分别是{2,2}、{2,3}、{2,2,3}，其中{2,3}的几何平均值最大，故输出其位置1和长度2
示例2
输入：
10 2
0.2
0.1
0.2
0.2
0.2
0.1
0.2
0.2
0.2
0.2
输出：
2 2
说明：
有多个长度至少为2的子数组的几何平均值为0.2，其中长度最短的为2，也有多个，长度为2且几何平均值为0.2的子数组最前面的那个为从第二个数开始的两个0.2组成的子数组
解题思路：
这道题正确率为0，大家看看还有什么没有注意到的！
如例1：
3 2
2
2
3
当长度为2时：
2,2 ：2*2=4；2,3 ：2*3=6；最大值为6，几何平均值为2.449489742783178，索引为1，长度为2
当长度为3时：
2,2,3 ：2*2*3=12；最大值为12,索引为0，长度为3，几何平均值为2.2894284851066637<2.449489742783178
最终结果：索引1，长度2

代码实现：

package com.codernav.demo.hwod.exam;

import java.math.BigDecimal;
import java.util.Scanner;

/**
 * @title 几何平均值最大子数组
 * @Description 从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大子数组，并输出其位置和大小。（K个数的几何平均值为K个数的乘积的K次方根）
 * 若有多个子数组的几何平均值均为最大值，则输出长度最小的子数组。
 * 若有多个长度相同的子数组的几何平均值均为最大值，则输出最前面的子数组。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static double max;   //最大几何平均值
    public static int index;    //正在处理数据的索引

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int L = sc.nextInt();
        double[] doubles = new double[N];
        for (int i = 0; i < N; i++) {
            doubles[i] = sc.nextDouble();
        }
        int resIndex = 0;
        int resLen = 0;
        for (int i = L; i <= N; i++) {
            if (handle(i, doubles)) {
                resIndex = index;
                resLen = i;
            }
        }
        System.out.println(resIndex + " " + resLen);
    }

    /**
     * 是否满足最大几何平均值
     *
     * @param len     子数组长度
     * @param doubles 输入的正数数组
     * @return
     */
    public static boolean handle(int len, double[] doubles) {
        double maxInLen = 1;    //len长度数组的最大乘积
        for (int i = 0; i < len; i++) {
            BigDecimal num1 = new BigDecimal(String.valueOf(maxInLen));
            BigDecimal num2 = new BigDecimal(String.valueOf(doubles[i]));
            maxInLen = num1.multiply(num2).doubleValue();   //初始化maxInLen
        }

        index = 0;      //初始化索引位置
        double count = maxInLen;    //各数组中数字的乘积
        for (int i = len; i < doubles.length; i++) {
            //如例1： 1 2 3 长度为2
            //第一个子数组{1,2}  乘积为 1 * 2 = 2
            //第二个子数组{2,3}  乘积为 2 * 3 / 1 = 6
            //相当于滑窗，第一个数组的乘积 * 紧接着后面的第一个数 / 第一个数组的第一个数 = 紧接着后面的数组的乘积
            count *= doubles[i] / doubles[i - len];
            if (count > maxInLen) {       //count大于maxInLen需要更新index和maxInLen
                index = i - len + 1;
                maxInLen = count;
            }
        }
        double CFG = Math.pow(maxInLen, (double) 1 / len);   //求出乘积的Len次方根
        if (CFG > max) {
            max = CFG;
            return true;
        }
        return false;
    }
}