title: Maximum Average Sum Partition Array
signature: def maximumAverageSumPartitionArray(a: List[Int], k: Int) = {
source_py: def maximum_average_sum_partition_array(A, K):
      n = len(A)
      pre_sum = ([0] * (n + 1))
      pre_sum[0] = 0
      for i in range(n):
          pre_sum[(i + 1)] = (pre_sum[i] + A[i])
      dp = ([0] * n)
      sum = 0
      for i in range(n):
          dp[i] = ((pre_sum[n] - pre_sum[i]) / (n - i))
      for k in range((K - 1)):
          for i in range(n):
              for j in range((i + 1), n):
                  dp[i] = max(dp[i], (((pre_sum[j] - pre_sum[i]) / (j - i)) + dp[j]))
      return int(dp[0])
source_cpp: double maximum_average_sum_partition_array(vector < int > & A, int K) {
    int n = A . size ( );
    double pre_sum [ n + 1 ];
    pre_sum [ 0 ] = 0;
    for ( int i = 0;
    i < n;
    i ++ ) pre_sum [ i + 1 ] = pre_sum [ i ] + A [ i ];
    double dp [ n ] = {
      0 };
      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 ] = max ( dp [ i ], ( pre_sum [ j ] - pre_sum [ i ] ) / ( j - i ) + dp [ j ] );
      return dp [ 0 ];
    }