813.md

813. Largest Sum of Averages

Solution 1 (time O(n^2*k), space O(nk))

class Solution(object):
    def largestSumOfAverages(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        n = len(nums)
        prefix_sum = [0 for _ in range(n + 1)]
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]
        dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            dp[i][1] = prefix_sum[i] / float(i)
        for j in range(2, k + 1):
            for i in range(j, n + 1):
                for t in range(j - 1, i):
                    dp[i][j] = max(dp[i][j], dp[t][j - 1] + (prefix_sum[i] - prefix_sum[t]) / float(i - t))
        return dp[n][k]