Largest Sum of Averages LeetCode solution in Python

1
class Solution:
2
    def largestSumOfAverages(self, A, k):
3
        n = len(A)
4
        dp = [0] * n
5
        sum = 0
6
        for i in range(n - 1, -1, -1):
7
            sum += A[i]
8
            dp[i] = sum / (n - i)
9
        for l in range(1, k):
10
            for i in range(n - l):
11
                sum = 0
12
                for j in range(i, n - l):
13
                    sum += A[j]
14
                    dp[i] = max(dp[i], dp[j + 1] + sum / (j - i + 1))
15
        return dp[0]