813.md

813 Largest Sum of Averages

Description

link

---

Solution (MEMO + DFS)

memo[n, k] : restore the ans of A[:n] in K times divided

Recursive :

• if n < k : return 0
• if k == 1 : return sum(A[:n]) / float(n)
• else : return max(memo[n, k], dfs(i, k - 1) + cur / float(n - i)) for i in range(n - 1, 0, -1) (cur += A[i])

---

Code

Complexity T : O(NK) M : O(NK)

class Solution:
    def largestSumOfAverages(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: float
        """
        memo = {}

        def dfs(n, k):
            if (n, k) in memo:
                return memo[n, k]

            if n < k:
                return 0

            memo[n, k] = 0

            if k == 1:
                memo[n, k] = sum(A[:n]) / float(n)
            else:
                cur = 0
                for i in range(n - 1, 0, -1):
                    cur += A[i]
                    memo[n, k] = max(memo[n, k], dfs(i, k - 1) + cur / float(n - i))
                    
            return memo[n, k]

        return dfs(len(A), K)