java - 平均数的最大总和

Question

Problem Statement :

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

我特别想了解集合生成背后的方法。考虑以下示例数组。

N= 5, Elements: [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]

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

问题:

I added logs to understand how these sets are generated. I am unable to understand how the sets [9,1,2] [3,9,8] will be generated using the following code snippet. More importantly how does it cover all possible setups upto size 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;
  }

Answer 1

您实际上不需要覆盖所有可能的设置，直到大小 3，因为您将总是想要使用您可用的最大组数(假设所有值都是正数)。

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