# Maximum average sum partition of an array

Given an array, we partition a row of numbers A into at most K adjacent (non-empty) groups, then the score is the sum of the average of each group. What is the maximum score that can be scored?

Examples:

Input : A = { 9, 1, 2, 3, 9 }
K = 3
Output : 20
Explanation : We can partition A into , [1, 2, 3], . The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], , [3, 9]. That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Input : A[] = { 1, 2, 3, 4, 5, 6, 7 }
K = 4
Output : 20.5
Explanation : We can partition A into [1, 2, 3, 4], , , . The answer is 2.5 + 5 + 6 + 7 = 20.5.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is to use recursion. An efficient solution is memorization where we keep the largest score upto k i.e. for 1, 2, 3… upto k;

Let memo[i][k] be the best score portioning A[i..n-1] into at most K parts. In the first group, we partition A[i..n-1] into A[i..j-1] and A[j..n-1], then our candidate partition has score average(i, j) + score(j, k-1)), where average(i, j) = (A[i] + A[i+1] + … + A[j-1]) / (j – i). We take the highest score of these.

In total, our recursion in the general case is :
memo[n][k] = max(memo[n][k], score(memo, i, A, k-1) + average(i, j))
for all i from n-1 to 1 .

div class="responsive-tabs">

## C++

 `// CPP program for maximum average sum partition ` `#include ` `using` `namespace` `std; ` ` `  `#define MAX 1000 ` ` `  `double` `memo[MAX][MAX]; ` ` `  `// bottom up approach to calculate score ` `double` `score(``int` `n, vector<``int``>& A, ``int` `k) ` `{ ` `    ``if` `(memo[n][k] > 0) ` `        ``return` `memo[n][k]; ` `    ``double` `sum = 0; ` `    ``for` `(``int` `i = n - 1; i > 0; i--) { ` `        ``sum += A[i]; ` `        ``memo[n][k] = max(memo[n][k], score(i, A, k - 1) + ` `                                          ``sum / (n - i)); ` `    ``} ` `    ``return` `memo[n][k]; ` `} ` ` `  `double` `largestSumOfAverages(vector<``int``>& A, ``int` `K) ` `{ ` `    ``int` `n = A.size(); ` `    ``double` `sum = 0; ` `    ``memset``(memo, 0.0, ``sizeof``(memo)); ` `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``sum += A[i]; ` ` `  `        ``// storing averages from starting to each i ;  ` `        ``memo[i + 1] = sum / (i + 1); ` `    ``} ` `    ``return` `score(n, A, K); ` `} ` ` `  `int` `main() ` `{ ` `    ``vector<``int``> A = { 9, 1, 2, 3, 9 }; ` `    ``int` `K = 3; ``// atmost partioning size ` `    ``cout << largestSumOfAverages(A, K) << endl; ` `    ``return` `0; ` `} `

## Python3

# Python3 program for maximum average sum partition
MAX = 1000

memo = [[0.0 for i in range(MAX)]
for i in range(MAX)]

# bottom up approach to calculate score
def score(n, A, k):
if (memo[n][k] > 0):
return memo[n][k]
sum = 0
i = n – 1
while(i > 0):
sum += A[i]
memo[n][k] = max(memo[n][k], score(i, A, k – 1) +
int(sum / (n – i)))

i -= 1

return memo[n][k]

def largestSumOfAverages(A, K):
n = len(A)
sum = 0
for i in range(n):
sum += A[i]

# storing averages from starting to each i ;
memo[i + 1] = int(sum / (i + 1))

return score(n, A, K)

# Driver Code
if __name__ == ‘__main__’:
A = [9, 1, 2, 3, 9]
K = 3 # atmost partioning size
print(largestSumOfAverages(A, K))

# This code is contributed by
# Surendra_Gangwar

Output:

```20
```

Above problem can now be easily understood as dynamic programming.
Let dp(i, k) be the best score partioning A[i:j] into at most K parts. If the first group we partition A[i:j] into ends before j, then our candidate partition has score average(i, j) + dp(j, k-1)). Recursion in the general case is dp(i, k) = max(average(i, N), (average(i, j) + dp(j, k-1))). We can precompute the prefix sums for fast execution of out code.

 `// CPP program for maximum average sum partition ` `#include ` `using` `namespace` `std; ` ` `  `double` `largestSumOfAverages(vector<``int``>& A, ``int` `K) ` `{ ` `    ``int` `n = A.size(); ` ` `  `    ``// storing prefix sums ` `    ``double` `pre_sum[n+1];  ` `    ``pre_sum = 0; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``pre_sum[i + 1] = pre_sum[i] + A[i]; ` ` `  `    ``// for each i to n storing averages  ` `    ``double` `dp[n] = {0}; ` `    ``double` `sum = 0; ` `    ``for` `(``int` `i = 0; i < n; i++)  ` `        ``dp[i] = (pre_sum[n] - pre_sum[i]) / (n - i); ` `     `  `    ``for` `(``int` `k = 0; k < K - 1; k++)  ` `        ``for` `(``int` `i = 0; i < n; i++)  ` `            ``for` `(``int` `j = i + 1; j < n; j++)  ` `                ``dp[i] = max(dp[i], (pre_sum[j] - ` `                         ``pre_sum[i]) / (j - i) + dp[j]); ` `     `  `    ``return` `dp; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``vector<``int``> A = { 9, 1, 2, 3, 9 }; ` `    ``int` `K = 3; ``// atmost partioning size ` `    ``cout << largestSumOfAverages(A, K) << endl; ` `    ``return` `0; ` `} `

Output:

```20
```