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 1000double memo[MAX][MAX];// bottom up approach to calculate scoredouble 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 partitionMAX = 1000memo = [[0.0 for i in range(MAX)] for i in range(MAX)]# bottom up approach to calculate scoredef 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 Codeif __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 partitionlet MAX = 1000;let memo = new Array(MAX).fill(0).map(() => new Array(MAX).fill(0));// bottom up approach to calculate scorefunction 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 sizedocument.write(largestSumOfAverages(A, K) + "<br>");</script> |
Output
20
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 codeint 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 partitionimport 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 codepublic 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 partitiondef 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 codeA = [ 9, 1, 2, 3, 9 ];K = 3; # atmost partitioning sizeprint(largestSumOfAverages(A, K));# This code is contributed by Rajput-Ji |
C#
// C# program for maximum average sum partitionusing 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 codepublic 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
20
Time Complexity: O(n2*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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
