Maximum average sum partition of an array | JavaScript program for maximum average sum partition ; bottom up approach to calculate score ; storing averages from starting to each i ; ; Driver code ; atmost partitioning size
let MAX = 1000 ; let memo = new Array ( MAX ) . fill ( 0 ) . map ( ( ) => new Array ( MAX ) . fill ( 0 ) ) ; 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 ] ; memo [ i + 1 ] [ 1 ] = sum / ( i + 1 ) ; } return score ( n , A , K ) ; } let A = [ 9 , 1 , 2 , 3 , 9 ] ; let K = 3 ; document . write ( largestSumOfAverages ( A , K ) + " " ) ;