Maximum average sum partition of an array | Python3 program for maximum average sum partition ; bottom up approach to calculate score ; storing averages from starting to each i ; ; Driver Code ; atmost partitioning size
MAX = 1000 NEW_LINE memo = [ [ 0.0 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE def score ( n , A , k ) : NEW_LINE INDENT if ( memo [ n ] [ k ] > 0 ) : NEW_LINE INDENT return memo [ n ] [ k ] NEW_LINE DEDENT sum = 0 NEW_LINE i = n - 1 NEW_LINE while ( i > 0 ) : NEW_LINE INDENT sum += A [ i ] NEW_LINE memo [ n ] [ k ] = max ( memo [ n ] [ k ] , score ( i , A , k - 1 ) + int ( sum / ( n - i ) ) ) NEW_LINE i -= 1 NEW_LINE DEDENT return memo [ n ] [ k ] NEW_LINE DEDENT def largestSumOfAverages ( A , K ) : NEW_LINE INDENT n = len ( A ) NEW_LINE sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += A [ i ] NEW_LINE memo [ i + 1 ] [ 1 ] = int ( sum / ( i + 1 ) ) NEW_LINE DEDENT return score ( n , A , K ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 9 , 1 , 2 , 3 , 9 ] NEW_LINE K = 3 NEW_LINE print ( largestSumOfAverages ( A , K ) ) NEW_LINE DEDENT