new_contents: # Time:  O(k * n^2)
  # Space: O(n)
  
  # We partition a row of numbers A into at most K adjacent (non-empty) groups,
  # then our score is the sum of the average of each group. What is the largest
  # score we can achieve?
  #
  # Note that our partition must use every number in A, and that scores are not
  # necessarily integers.
  #
  # Example:
  # Input:
  # A = [9,1,2,3,9]
  # K = 3
  # Output: 20
  # Explanation:
  # The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is
  # 39 + (1 + 2 + 3) / 3 + 9 = 20.
  # We could have also partitioned A into [9, 1], [2], [3, 9], for example.
  # That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
  #
  # Note:
  # - 1 <= A.length <= 100.
  # - 1 <= A[i] <= 10000.
  # - 1 <= K <= A.length.
  # Answers within 10^-6 of the correct answer will be accepted as correct.
  
  try:
      xrange          # Python 2
  except NameError:
      xrange = range  # Python 3
  
  
  class Solution(object):
      def largestSumOfAverages(self, A, K):
          """
          :type A: List[int]
          :type K: int
          :rtype: float
          """
          accum_sum = [A[0]]
          for i in xrange(1, len(A)):
              accum_sum.append(A[i]+accum_sum[-1])
  
          dp = [[0]*len(A) for _ in xrange(2)]
          for k in xrange(1, K+1):
              for i in xrange(k-1, len(A)):
                  if k == 1:
                      dp[k % 2][i] = float(accum_sum[i])/(i+1)
                  else:
                      for j in xrange(k-2, i):
                          dp[k % 2][i] = \
                              max(dp[k % 2][i],
                                  dp[(k-1) % 2][j] +
                                  float(accum_sum[i]-accum_sum[j])/(i-j))
          return dp[K % 2][-1]
  
subject: Add largest-sum-of-averages.py