CODEWITHSUNDEEP
javaalgorithmdynamic-programming
Henry Chang
Henry Chang

Reputation: 31

Largest Sum of Averages

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.

I am specifically trying to understand the approach behind the set generation . Consider following example array.

N= 5, Elements: [9,1,2,3,9,8]

k = 3

The questions asks to generate steps up-to size k. For instance, we can have following generated sets (though the actual set would be larger).

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

I am trying to understand the naive recursive solution with no memoization.

Question:

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

Upvotes: 3

Views: 403

Answers (2)

David Alvarez
David Alvarez

Reputation: 1286

I do not understand the algorithm but what I would do is trying to do the example with my head, to understand how the code works. Here I made the first iteration of the loop :

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

Which corresponds to the sum of the average of [9,1,2], [3], [9, 8]

Each 1), 2),... is a recursion and all the values between <> is know in the reverse order (when going back up from the recursion)

Try to continue to understand ! Good luck !

Upvotes: 0

hbejgel
hbejgel

Reputation: 4847

You do not really need to cover all possible setups up to size 3 because you will ALWAYS want to use the maximum number of groups available to you (assuming all values are positive).

Suppose that the group size is k and you found an optimal answer with k-1 groups. If you take one of these groups, take the highest value from it and put it into its own group then you'd have a higher or equal score, therefore your answer was not really optimal. (The average of n numbers is never higher than the largest of those numbers)

Upvotes: 1

Related Questions