Maximum average sum partition of an array | Java program for maximum average sum partition ; bottom up approach to calculate score ; storing averages from starting to each i ; ; Driver code ; atmost partitioning size
import java . util . Arrays ; import java . util . Vector ; class GFG { static int MAX = 1000 ; static double [ ] [ ] memo = new double [ MAX ] [ MAX ] ; 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 ) ; memo [ i + 1 ] [ 1 ] = sum / ( i + 1 ) ; } return score ( n , A , K ) ; } 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 ) ) ; } }