时间戳

首页 > 解决方案 > 最大平均数

java - 最大平均数

问题描述

问题陈述：

我们将一行数字 A 划分为最多 K 个相邻（非空）组，然后我们的分数是每个组的平均值之和。我们能达到的最大分数是多少？

请注意，我们的分区必须使用 A 中的每个数字，并且分数不一定是整数。

我特别想了解 set generation 背后的方法。考虑以下示例数组。

N= 5，元素：[9,1,2,3,9,8]

k = 3

这些问题要求生成最大为 k 的步骤。例如，我们可以有以下生成的集合（尽管实际的集合会更大）。

  • [9,1,2] & [3,9,8]
  • [9], [1,2,3], [9, 8]
  • [9,1,2], [3], [9, 8]

我试图理解没有记忆的朴素递归解决方案。

问题：

我添加了日志以了解这些集合是如何生成的。我无法理解如何使用以下代码片段生成集合 [9,1,2] [3,9,8]。更重要的是，它如何涵盖最大尺寸为 3 的所有可能设置。

  public double largestSumOfAverages(int[] arr, int groupSize) {
    int[] sum = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
      sum[i] = arr[i] + (i > 0 ? sum[i - 1] : 0);
    }

    System.out.println(Arrays.toString(sum));
    return dfs(arr, groupSize, sum, arr.length, 0);
  }

  public double dfs(int[] arr, int groupSize, int[] sumToIthIndex, int right, int left) {
    if (groupSize == 1) {
      double avg1 = ((double) (sumToIthIndex[right - 1] - sumToIthIndex[left] + arr[left]) / (right
          - left));

      System.out.println(" dfs return :: " + left + " right:: " + right + "  :grpSize:: " + groupSize);
      return avg1;
    }
    double num = 0;
    for (int index = left; index + groupSize <= right; index++) {
      System.out.println(" dfs left:: " + index + " right:: " + right + "  :grpSize:: " + groupSize);
      num = Math.max(num,
          ((double) (sumToIthIndex[index] - sumToIthIndex[left] + arr[left]) / (index - left
              + 1)) + dfs(arr, groupSize - 1, sumToIthIndex, right,index + 1));
    }
    System.out.println("End");
    return num;
  }

标签： javaalgorithmdynamic-programming

解决方案

您实际上并不需要涵盖最大为 3 的所有可能设置，因为您将ALWAYS希望使用可用的最大组数（假设所有值都是正数）。

假设组大小为k并且您找到了组的最佳答案k-1。如果您选择其中一个组，从中取最高值并将其放入自己的组中，那么您将获得更高或相等的分数，因此您的答案并不是最佳的。（n 个数字的平均值永远不会高于这些数字中的最大值）

推荐阅读