Maximum average sum partition of an array | CPP program for maximum average sum partition ; bottom up approach to calculate score ; storing averages from starting to each i ; ; Driver code ; atmost partitioning size
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000 NEW_LINE double memo [ MAX ] [ MAX ] ; double score ( int n , vector < int > & 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 [ i ] ; memo [ n ] [ k ] = max ( memo [ n ] [ k ] , score ( i , A , k - 1 ) + sum / ( n - i ) ) ; } return memo [ n ] [ k ] ; } double largestSumOfAverages ( vector < int > & A , int K ) { int n = A . size ( ) ; double sum = 0 ; memset ( memo , 0.0 , sizeof ( memo ) ) ; for ( int i = 0 ; i < n ; i ++ ) { sum += A [ i ] ; memo [ i + 1 ] [ 1 ] = sum / ( i + 1 ) ; } return score ( n , A , K ) ; } int main ( ) { vector < int > A = { 9 , 1 , 2 , 3 , 9 } ; int K = 3 ; cout << largestSumOfAverages ( A , K ) << endl ; return 0 ; }