Maximum average sum partition of an array | Python3 program for maximum average sum partition ; storing prefix sums ; for each i to n storing averages ; Driver code ; K = 3 ; atmost partitioning size
def largestSumOfAverages ( A , K ) : NEW_LINE INDENT n = len ( A ) ; NEW_LINE pre_sum = [ 0 ] * ( n + 1 ) ; NEW_LINE pre_sum [ 0 ] = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT pre_sum [ i + 1 ] = pre_sum [ i ] + A [ i ] ; NEW_LINE DEDENT dp = [ 0 ] * n ; NEW_LINE sum = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT dp [ i ] = ( pre_sum [ n ] - pre_sum [ i ] ) / ( n - i ) ; NEW_LINE DEDENT for k in range ( K - 1 ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , ( pre_sum [ j ] - pre_sum [ i ] ) / ( j - i ) + dp [ j ] ) ; NEW_LINE DEDENT DEDENT DEDENT return int ( dp [ 0 ] ) ; NEW_LINE DEDENT A = [ 9 , 1 , 2 , 3 , 9 ] ; NEW_LINE print ( largestSumOfAverages ( A , K ) ) ; NEW_LINE