Самая большая сумма средних

Question

Постановка проблемы :

Разобьем ряд чисел A на самое большее K смежных (непустых) групп, то наша оценка является суммой среднего значения для каждой группы. Какие самый большой результат, который мы можем достичь?

Обратите внимание, что наш раздел должен использовать каждое число в A, и это означает, что не обязательно целые числа.

Я специально пытаюсь понять подход к созданию множества. Рассмотрим следующий пример массива.

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;
  }

Answer 1

На самом деле вам не нужно охватывать все возможные установки до размера 3, потому что вы ALWAYS захотите использовать максимальное количество доступных вам групп (при условии, что все значения положительны).

Предположим, что размер группы k, и вы нашли оптимальный ответ с k-1 группами. Если вы возьмете одну из этих групп, возьмете наибольшее значение из нее и поместите ее в свою собственную группу, тогда у вас будет более высокий или равный балл, поэтому ваш ответ не был действительно оптимальным. (Среднее из n чисел никогда не бывает больше, чем наибольшее из этих чисел)

Answer 2

Я не понимаю алгоритм, но я попытался бы сделать пример с моей головой, чтобы понять, как работает код. Здесь я сделал первую итерацию цикла:

FIRST ITERATION
1) groupeSize = 3, right = 6, left = 0, index = 0, 
    num = max(0, ((9 - 9 + 9) / 1) + <5.5>)) = 14.5
2) groupeSize = 2, right = 6, left = 1, index = 0,
    num1 = max(0, ((9 - 10 + 1 / (0 - 1 + 1)) + <5.5>)) = 5.5
3) groupeSize = 1, right = 6, left = 2, index = 0, avg1 = ((32 - 12 + 2) / (6-2)) = 5.5

Что соответствует сумме среднего [9,1,2], [3], [9, 8]

Каждый 1), 2), ... является рекурсией, и все значения между <> известны в обратном порядке (при возврате из рекурсии)

Попробуйте продолжить понимать! Удачи!