Maximum average sum partition of an array | Java program for maximum average sum partition ; storing prefix sums ; for each i to n storing averages ; Driver code ; int K = 3 ; atmost partitioning size
import java . util . * ; class GFG { static double largestSumOfAverages ( int [ ] A , int K ) { int n = A . length ; 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 ] ; 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 ] ; } public static void main ( String [ ] args ) { int [ ] A = { 9 , 1 , 2 , 3 , 9 } ; System . out . println ( largestSumOfAverages ( A , K ) ) ; } }