Maximum average sum partition of an array

0 0 8 minutes read

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 [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [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], [5], [6], [7]. The answer is 2.5 + 5 + 6 + 7 = 20.5.

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 .

Implementation:

C++

// CPP program for maximum average sum partition
#include <bits/stdc++.h>
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][1] = sum / (i + 1);
    }
    return score(n, A, K);
}
 
int main()
{
    vector<int> A = { 9, 1, 2, 3, 9 };
    int K = 3; // atmost partitioning size
    cout << largestSumOfAverages(A, K) << endl;
    return 0;
}

Java

// Java program for maximum average sum partition 
import java.util.Arrays;
import java.util.Vector;
 
class GFG 
{
 
    static int MAX = 1000;
    static double[][] memo = new double[MAX][MAX];
 
    // bottom up approach to calculate score
    public static double score(int n, Vector<Integer> 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.elementAt(i);
 
            memo[n][k] = Math.max(memo[n][k], 
                                  score(i, A, k - 1) +
                                  sum / (n - i));
        }
        return memo[n][k];
    }
 
    public static double largestSumOfAverages(Vector<Integer> A, int K)
    {
        int n = A.size();
        double sum = 0;
 
        for (int i = 0; i < memo.length; i++) 
        {
            for (int j = 0; j < memo[i].length; j++)
                memo[i][j] = 0.0;
        }
 
        for (int i = 0; i < n; i++) 
        {
            sum += A.elementAt(i);
 
            // storing averages from starting to each i ;
            memo[i + 1][1] = sum / (i + 1);
        }
 
        return score(n, A, K);
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        Vector<Integer> A = new Vector<>(Arrays.asList(9, 1, 2, 3, 9));
        int K = 3;
        System.out.println(largestSumOfAverages(A, K));
 
    }
}
 
// This code is contributed by sanjeev2552

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][1] = int(sum / (i + 1))
     
    return score(n, A, K)
 
# Driver Code
if __name__ == '__main__':
    A = [9, 1, 2, 3, 9]
    K = 3 # atmost partitioning size
    print(largestSumOfAverages(A, K))
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# program for maximum average sum partition 
using System;
using System.Collections.Generic;
 
class GFG 
{
    static int MAX = 1000;
    static double[,] memo = new double[MAX, MAX];
 
    // bottom up approach to calculate score
    public static double score(int n, 
                               List<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] = Math.Max(memo[n, k], 
                                  score(i, A, k - 1) +
                                  sum / (n - i));
        }
        return memo[n, k];
    }
 
    public static double largestSumOfAverages(List<int> A, 
                                                   int K)
    {
        int n = A.Count;
        double sum = 0;
 
        for (int i = 0;
                 i < memo.GetLength(0); i++) 
        {
            for (int j = 0;
                     j < memo.GetLength(1); j++)
                memo[i, j] = 0.0;
        }
 
        for (int i = 0; i < n; i++) 
        {
            sum += A[i];
 
            // storing averages from
            // starting to each i;
            memo[i + 1, 1] = sum / (i + 1);
        }
 
        return score(n, A, K);
    }
 
    // Driver code
    public static void Main(String[] args) 
    {
        int [] arr = {9, 1, 2, 3, 9};
        List<int> A = new List<int>(arr);
        int K = 3;
        Console.WriteLine(largestSumOfAverages(A, K));
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for maximum average sum partition
 
 
let MAX = 1000;
 
let memo = new Array(MAX).fill(0).map(() => new Array(MAX).fill(0));
 
// bottom up approach to calculate score
function score(n, A, k) {
    if (memo[n][k] > 0)
        return memo[n][k];
    let sum = 0;
    for (let i = n - 1; i > 0; i--) {
        sum += A[i];
        memo[n][k] = Math.max(memo[n][k], score(i, A, k - 1) +
            sum / (n - i));
    }
    return memo[n][k];
}
 
function largestSumOfAverages(A, K) {
    let n = A.length;
    let sum = 0;
 
    for (let i = 0; i < n; i++) {
        sum += A[i];
 
        // storing averages from starting to each i ;
        memo[i + 1][1] = sum / (i + 1);
    }
    return score(n, A, K);
}
 
 
let A = [9, 1, 2, 3, 9];
let K = 3; // atmost partitioning size
document.write(largestSumOfAverages(A, K) + "<br>");
 
</script>

Output

Above problem can now be easily understood as dynamic programming.

Let dp(i, k) be the best score partitioning 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.

Implementation:

C++

// CPP program for maximum average sum partition
#include <bits/stdc++.h>
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] = 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[0];
}
 
// Driver code
int main()
{
    vector<int> A = { 9, 1, 2, 3, 9 };
    int K = 3; // atmost partitioning size
    cout << largestSumOfAverages(A, K) << endl;
    return 0;
}

Java

// Java program for maximum average sum partition
import java.util.*;
 
class GFG 
{
 
static double largestSumOfAverages(int[] A, int K)
{
    int n = A.length;
 
    // storing prefix sums
    double []pre_sum = new double[n + 1]; 
    pre_sum[0] = 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 = new double[n];
    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] = Math.max(dp[i], (pre_sum[j] -
                        pre_sum[i]) / (j - i) + dp[j]);
     
    return dp[0];
}
 
// Driver code
public static void main(String[] args) 
{
    int []A = { 9, 1, 2, 3, 9 };
    int K = 3; // atmost partitioning size
    System.out.println(largestSumOfAverages(A, K));
}
}
 
// This code is contributed by PrinciRaj1992 

Python3

# Python3 program for maximum average 
# sum partition
def largestSumOfAverages(A, K):
 
    n = len(A);
 
    # storing prefix sums
    pre_sum = [0] * (n + 1); 
    pre_sum[0] = 0;
    for i in range(n):
        pre_sum[i + 1] = pre_sum[i] + A[i];
 
    # for each i to n storing averages 
    dp = [0] * n;
    sum = 0;
    for i in range(n):
        dp[i] = (pre_sum[n] -
                 pre_sum[i]) / (n - i);
     
    for k in range(K - 1):
        for i in range(n):
            for j in range(i + 1, n): 
                dp[i] = max(dp[i], (pre_sum[j] -
                                    pre_sum[i]) /
                                    (j - i) + dp[j]);
     
    return int(dp[0]);
 
# Driver code
A = [ 9, 1, 2, 3, 9 ];
K = 3; # atmost partitioning size
print(largestSumOfAverages(A, K));
 
# This code is contributed by Rajput-Ji

C#

// C# program for maximum average sum partition
using System;
using System.Collections.Generic;
     
class GFG 
{
static double largestSumOfAverages(int[] A,
                                   int K)
{
    int n = A.Length;
 
    // storing prefix sums
    double []pre_sum = new double[n + 1]; 
    pre_sum[0] = 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 = new double[n];
    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] = Math.Max(dp[i], (pre_sum[j] -
                        pre_sum[i]) / (j - i) + dp[j]);
     
    return dp[0];
}
 
// Driver code
public static void Main(String[] args) 
{
    int []A = { 9, 1, 2, 3, 9 };
    int K = 3; // atmost partitioning size
    Console.WriteLine(largestSumOfAverages(A, K));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// javascript program for maximum average sum partition
 
    function largestSumOfAverages(A , K) {
        var n = A.length;
 
        // storing prefix sums
        var pre_sum = Array(n + 1).fill(-1);
        pre_sum[0] = 0;
        for (var i = 0; i < n; i++)
            pre_sum[i + 1] = pre_sum[i] + A[i];
 
        // for each i to n storing averages
        var dp = Array(n).fill(-1);
        var sum = 0;
        for (var i = 0; i < n; i++)
            dp[i] = (pre_sum[n] - pre_sum[i]) / (n - i);
 
        for (k = 0; k < K - 1; k++)
            for (i = 0; i < n; i++)
                for (j = i + 1; j < n; j++)
                    dp[i] = Math.max(dp[i], (pre_sum[j] - pre_sum[i]) / (j - i) + dp[j]);
 
        return dp[0];
    }
 
    // Driver code
        var A = [ 9, 1, 2, 3, 9 ];
        var K = 3; // atmost partitioning size
        document.write(largestSumOfAverages(A, K));
 
// This code is contributed by umadevi9616 
</script>

Output

Time Complexity: O(n²*K)
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!