Problem Link

dp[i][k] := largest average sum of nums[i:] with k partitions

class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        L = len(nums)
        dp = [[0 for _ in range(k+1)] for _ in range(L)]
        # presum
        presum = [0] * (L+1)
        for i in range(1, L+1):
            presum[i] = nums[i-1] + presum[i-1]
        # initialization
        for i in range(L):
            dp[i][1] = (presum[L] - presum[i]) / (L-i)
        # dp
        for kk in range(2, k+1): # number of partitions
            for i in range(L-1):
                for j in range(i+1, L):
                    dp[i][kk] = max(dp[i][kk], (presum[j] - presum[i]) / (j-i) + dp[j][kk-1])
        return dp[0][k]