求数组子序列的最大可能平均值——寻求高效解决方案

首先，我们得抓住问题的核心：要最大化子序列的平均值，本质就是最大化子序列总和与元素个数的比值。你之前用的O(n²)解法在n达到10^{5时完全行不通，因为10}10级别的计算量根本没法在合理时间内完成。下面我会给出两种场景下的高效解法，轻松处理大规模输入。

核心思路拆解 #

根据问题中“参与平均值计算的元素个数”的约束，分两种常见场景处理：

场景1：必须选取恰好m个元素的子序列 #

因为平均值 = 总和 / m，所以最大化平均值等价于最大化总和。而总和最大的子序列，必然是数组里最大的m个元素的集合（子序列不要求连续，只要元素来自数组且不重复选取）。

举个修正后的合理示例：

输入：5 3 1 2 3 4 5，选3个最大元素3、4、5，总和12，平均值12/3=4，这才是正确的最大平均值（原示例描述可能存在笔误）。

场景2：可以选取任意长度的子序列（长度≥1） #

这时最大平均值就是数组中的最大元素——单个最大元素的平均值就是它本身，任何包含多个元素的子序列的平均值都不会超过这个值（毕竟其他元素都≤最大元素，总和≤k*max_element，平均值自然≤max_element）。

高效实现方案 #

方法1：排序法（简单直观） #

把数组排序后，取最后m个元素求和，再除以m即可。

• 时间复杂度：O(n log n)，对于n=10^5来说完全能跑通。
• Java代码示例：

import java.util.Arrays;
import java.util.Scanner;

public class MaxAverage {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        long sum = 0;
        // 取排序后最后m个元素求和
        for (int i = n - m; i < n; i++) {
            sum += arr[i];
        }
        double maxAvg = (double) sum / m;
        // 若要求输出整数（如示例），可按需取整
        System.out.println((int) maxAvg);
    }
}

方法2：最小堆法（更高效，适合m较小的情况） #

因为m≤10^3，我们可以用一个大小为m的最小堆，遍历数组时维护堆里是当前最大的m个元素：

• 遍历数组，堆未满时直接加元素；
• 若当前元素比堆顶大，就弹出堆顶，加入当前元素；
• 遍历结束后，堆里的元素就是最大的m个，求和算平均值。
• 时间复杂度：O(n log m)，m=10^3时log m≈10，n=10^5时总操作数仅约1e6，速度非常快。
• Java代码示例：

import java.util.PriorityQueue;
import java.util.Scanner;

public class MaxAverage {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(m);
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            if (minHeap.size() < m) {
                minHeap.add(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.add(num);
            }
        }
        long sum = 0;
        while (!minHeap.isEmpty()) {
            sum += minHeap.poll();
        }
        double maxAvg = (double) sum / m;
        System.out.println((int) maxAvg);
    }
}

为什么O(n²)解法不能用？ #

O(n²)解法一般是枚举所有可能的子序列/子数组，计算平均值并记录最大值。但n=10^5时，n²=1e10，这个量级的计算量哪怕是超级计算机都得跑很久，而我们的解法时间复杂度是线性对数级，完全能在几秒内处理完大规模输入。

内容的提问来源于stack exchange，提问作者Deepu--Java