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 9 + (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.

Difficulty: interview

Starter code:

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        

Solutions:
class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        #if not A: return 0
        #if len(A)==1: return A[0]
        # Real Run Time is a little bit UNSTABLE
        N = len(A)
        P = [0] * (N+1)
        for i in range(1,N+1): P[i] = P[i-1] + A[i-1]
        
        # Table[a] = optimal for A[a:] with k subsets, initially k=1
        Table = [(P[N]-P[i])/(N-i) for i in range(N)]
        for k in range(2, K+1):
            for i in range(K-k,N-k+1):
                Table[i] = max((P[j]-P[i])/(j-i) + Table[j] for j in range(i+1,N-k+2))
        
        return Table[0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:

        N = len(A)
        P = [0] * (N+1)
        for i in range(1,N+1): 
            P[i] = P[i-1] + A[i-1]
            
        dp = [(P[N]-P[i])/(N-i) for i in range(N)]
        for k in range(1,K):
            for i in range(K-k-1,N-k):
                dp[i] = max((P[j]-P[i])/(j-i) + dp[j] for j in range(i+1,N-k+1))
                
        return dp[0]

from functools import lru_cache
from itertools import accumulate
class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        n = len(A)
        p = [0] + list(accumulate(A))
        @lru_cache(None)
        def dp(l,k):
            if k > l:
                return 0
            if k == 1:
                return p[l] / l
            return max(dp(i,k-1) + (p[l] - p[i])/(l-i) for i in range(k-1,l))
        return dp(n,K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        n = len(A)
        memo = [[0 for k in range(K)] for i in range(n)]
        
        def aux(A, cur, k, memo):
            if cur == len(A):
                return 0
            if memo[cur][k]:
                return memo[cur][k]
            tmp = sum(A[cur:])/(len(A)-cur)
            if k == 0:
                memo[cur][k] = tmp
                return tmp
            for i in range(cur+1, len(A)+1):
                tmp = max(tmp, sum(A[cur:i])/(i-cur) + aux(A, i, k-1, memo))
            memo[cur][k] = tmp
            return tmp
                
        return aux(A, 0, K-1, memo)
        


class Solution:
    def largestSumOfAverages(self, A, K: int) -> float:
        A = [0] + A
        len_a = len(A)
        dp = [[0] * (K+1) for _ in range(len_a)]
        
        for i in range(1, len_a):
            dp[i][0] = -float('inf')
        
        for i in range(1, len_a):
            for k in range(1, min(K+1, i+1)):
                for j in range(k, i+1):
                    dp[i][k] = max(dp[i][k], dp[j-1][k-1] + self.helper(A[j:i+1]))
        return dp[-1][-1]
    
    def helper(self, sub_a):
        return sum(sub_a) / len(sub_a)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        P = [0] * (len(A)+1)
        for i, n in enumerate(A):
            P[i+1] = P[i]+n
        
        def average(i, j):
            return (P[j]-P[i]) / float(j-i)
        
        N = len(A)
        dp = [average(i,N) for i in range(N)]
        
        for k in range(K-1):
            for i in range(N):
                for j in range(i+1, N):
                    dp[i] = max(dp[i],average(i,j)+dp[j])
        return dp[0]
            


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        P = [0]
        for x in A: 
            P.append(P[-1] + x)
        
        def average(i, j):
            return (P[j] - P[i]) / float(j - i)

        N = len(A)
        dp = [average(i, N) for i in range(N)]
        print(dp)
        for k in range(K-1):
            for i in range(N):
                for j in range(i+1, N):
                    dp[i] = max(dp[i], average(i, j) + dp[j])

        return dp[0]
        
#         N = len(A)
#         cache = dict()
#         def getMaxScore(i,k):
#             if k <= 0:
#                 return 0
#             if (i,k) in cache:
#                 return cache[(i,k)]
            
#             maxScore = -float(\"inf\")
#             for j in range(i,N):
#                 leftArray = A[i:j+1]
#                 # print(leftArray)
#                 score = float(sum(leftArray))/len(leftArray) + getMaxScore(min(j+1,N),k-1)
#                 maxScore = max(maxScore,score)
                
#             cache[(i,k)] = maxScore
#             return maxScore
        
#         return getMaxScore(0,K)
                


class Solution(object):
    def largestSumOfAverages(self, A, K):
        prefix_sum = [0]
        for x in A:
            prefix_sum.append(prefix_sum[-1] + x)

        def average(i, j):
            return (prefix_sum[j] - prefix_sum[i]) / (j - i)

        n = len(A)
        dp = [[0] * n for _ in range(K)]

        for k in range(K):
            for i in range(n):
                if k == 0 and i == 0:
                    dp[0][i] = A[0]
                elif k == 0:
                    dp[0][i] = average(0, i+1)
                else:
                    for j in range(i):
                        dp[k][i] = max(dp[k][i], dp[k - 1][j] + average(i+1, j+1))

        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        P = [0] 
        for x in A: P.append(P[-1] +x)
        
        def average(i,j):
          return float(P[j] - P[i]) / float(j-i)
        
        N = len(A)
        
        dp = [average(i,N) for i in range(N)]
        
        for k in range(K-1):
          for i in range(N):
            for j in range(i+1, N):
              dp[i] = max(dp[i], average(i,j) + dp[j])
        
        return dp[0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        memo = {}
        length = len(A)

        def dfs(start, k):
            if (start, k) in memo:
                return memo[(start, k)]
            if k == 1:
                memo[(start, k)] = sum(A[start:]) / (length - start)
                return memo[(start, k)]
            if start >= length:
                return 0

            value = 0
            for i in range(start + 1, length):
                val = sum(A[start:i]) / (i - start)
                value = max(value, dfs(i, k - 1) + val)
            memo[(start, k)] = value
            return value

        return dfs(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        s, dp = [0] + A, {}
        for i in range(1, len(A) + 1):
            s[i] += s[i - 1]
        #print(s)
        def dfs(i, k):
            #print(i, k)
            if k == 1:
                #print((s[-1] - s[i]) / (len(A) - i))
                return (s[-1] - s[i]) / (len(A) - i)
            if (i, k) in dp: return dp[(i, k)]
            dp[(i, k)] = max((s[j] - s[i]) / (j - i) + dfs(j, k - 1) for j in range(i + 1, len(A) - k + 2))
            return dp[(i, k)]
        return dfs(0, K)
        
                
                
                


import itertools

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # Dynamic Programming 
        # Time  complexity: O(K x N^2)
        # Space complexity: O(N)
        P = [0] + list(itertools.accumulate(A))
        def average(i, j): return (P[j] - P[i]) / float(j - i)

        N = len(A)
        dp = [average(i, N) for i in range(N)]
        for _ in range(K - 1):
            for i in range(N):
                for j in range(i + 1, N):
                    dp[i] = max(dp[i], average(i, j) + dp[j])

        return dp[0]





class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        cumsums = [0] * (len(A) + 1)
        for i, x in enumerate(A):
            cumsums[i+1] = cumsums[i] + A[i]
        
        memo = {}
        def DP(j, K):
            if K == 0:
                return 0 
            if j + 1 == K:
                return cumsums[j+1]
            if K == 1:
                return cumsums[j+1]/(j+1)
            
            res = 0
            for i in range(j, -1, -1):
                if (i, K-1) not in memo:
                    memo[(i, K-1)] = DP(i, K-1)
                if j - i == 0:
                    res = max(res, memo[(i, K-1)])
                else:
                    res = max(res, memo[(i, K-1)] + (cumsums[j + 1] - cumsums[i+1])/(j - i))
            return res
        
        a = DP(len(A)-1, K)
        return a
            


class Solution(object):
    def largestSumOfAverages(self, A, K):
        memo = {}
        def search(n, k):
            if (n, k) in memo: return memo[n, k]
            if n < k: return 0
            if k == 1:
                memo[n, k] = sum(A[:n]) / float(n)
                return memo[n, k]
            cur, memo[n, k] = 0, 0
            for i in range(n - 1, 0, -1):
                cur += A[i]
                memo[n, k] = max(memo[n, k], search(i, k - 1) + cur / float(n - i))
            return memo[n, k]
        return search(len(A), K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        Cum = [0]
        for i in range(len(A)):
            Cum.append(Cum[-1] + A[i])
        def Average(h,k):
            return (Cum[k] - Cum[h])/(k - h)
        
        dp = [Average(i, len(A)) for i in range(len(A))]
        for _ in range(K-1):
            for i in range(len(A)):
                for j in range(i+1,len(A)):
                    dp[i] = max(dp[i], Average(i,j) + dp[j])
        return dp[0]


class Solution(object):
    def largestSumOfAverages(self, A, K):
        P = [0]
        for x in A: P.append(P[-1] + x)
        def average(i, j):
            return (P[j] - P[i]) / float(j - i)

        N = len(A)
        dp = [average(i, N) for i in range(N)]
        for k in range(K-1):
            for i in range(N):
                for j in range(i+1, N):
                    dp[i] = max(dp[i], average(i, j) + dp[j])

        return dp[0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        presum = [0] + list(itertools.accumulate(A))
        def mean(i, j):
            return (presum[j+1] - presum[i])/(j-i+1)
        
        max_val = [0]
        def helper(i, j, k):
            if (i, j, k) in check:
                result = check[(i, j, k)]
            elif k == 1:
                result = mean(i, j)
            else:
                result = -float('inf')
                for mid in range(i, j):
                    result = max(result, mean(i, mid) + helper(mid+1, j, k-1))
            check[(i, j, k)] = result
            max_val[0] = max(max_val[0], result)
            return result
        n = len(A)
        check = {}
        helper(0, n-1, K)
        return max_val[0]

# dp[i][k] = largest sum of avg for A[:(i+1)] splitted into most k groups
# = max{max[dp[j][k-1]+avg(A[(j+1):(i+1)]) for j<i], dp[i][k-1]}
class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        import itertools
        cumsum = list(itertools.accumulate(A)) #if use mean, over time limit
#         print(\"cumsum\", cumsum)
        L = len(A)
        K = min(L, K)
        dp = [[0]*(K+1) for i in range(L)]
        for i in range(L):
            dp[i][1] = (cumsum[i])/(i+1) # we don't use dp[i][0]
        for k in range(2,K+1):
            for i in range(L):
                tmp = dp[i][k-1]
                for j in range(i):
                    tmp = max(tmp, dp[j][k-1]+(cumsum[i]-cumsum[j])/(i-j))
                dp[i][k] = tmp
#         print(dp)
        return dp[-1][K]         

class Solution:
    def largestSumOfAverages(self, A, K):
        P = [0]
        for x in A: P.append(P[-1] + x)
        def average(i, j):
            return (P[j] - P[i]) / (j - i)

        N = len(A)
        dp = [average(i, N) for i in range(N)]
        for k in range(K-1):
            for i in range(N):
                for j in range(i+1, N):
                    dp[i] = max(dp[i], average(i, j) + dp[j])

        return dp[0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # a recursive function where it gets each group from 1 to A-K2
        # the recursive function builds a tree, 
        # O(K^(N-K))
        # 9, 1,2,3, 9,6,7,8 , the state = (index, K2)
        def ave(list_):
            return sum(list_)/len(list_)
        dp = {}
        
        def rec(index, k):
            if index == len(A):
                return 0
            if (index,k) in dp:
                return dp[(index,k)]
            if k==1:
                return ave(A[index:])
            m=0
            for i in range(index+1,len(A)):
                m = max(m, ave(A[index:i]) + rec(i,k-1))
            dp[(index,k)] = m
            return m
        return rec(0,K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        L = len(A)
        dp = [
            [0 for _ in range(K + 1)] for _out in range(L)
        ]
        
        prefix_sum = [0 for _ in range(L + 1)]
        for i in range(1, L + 1):
            prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]

        dp[0][1] = A[0]
        for i in range(1, L):
            dp[i][1] = (prefix_sum[i] + A[i]) / (i + 1)
            
        # for i in dp:
        #     print(i)

        for i in range(1, L):
            for k in range(2, K + 1):
                if k > i + 1:
                    dp[i][k] = dp[i][k - 1]
                else:
                    for j in range(-1, i):
                        # this may be bottle neck
                        subarr = A[j + 1 : i + 1]
                        ave = (prefix_sum[i + 1] - prefix_sum[j + 1]) / (i - j)
                        if j == -1:
                            tmp = 0
                        else:
                            tmp = dp[j][k - 1]
                        if ave + tmp > dp[i][k]:
                            dp[i][k] = ave + tmp
                            
        # for i in dp:
        #     print(i)
        # print('done')
        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        h = {}
        def helper(curr, pos, k):
            if pos == len(A):
                return curr
            if k == 0:
                return float('-inf')
            if (pos, k) in h:
                return curr + h[(pos, k)]
            res = 0
            for i in range(pos, len(A)):
                temp = sum(A[pos : (i + 1)]) / (i - pos + 1)
                res = max(helper(temp, i + 1, k - 1), res)
            h[(pos, k)] = res
            return curr + res
        
        return helper(0, 0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        N = len(A)
        summary = [0] * (N + 1)
        for i, item in enumerate(A):
            summary[i + 1] = summary[i] + item
        dp = [[(summary[N] - summary[i]) / (N - i) for i in range(N)] for _ in range(K)]
        for remain in range(1, K):
            for i in range(N):
                for j in range(i + 1, N):
                    dp[remain][i] = max(dp[remain][i], (summary[j] - summary[i]) / (j - i) + dp[remain - 1][j])
        return dp[-1][0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        dp = {}
        def a(n,k):
            if n<k:return 0
            if (n,k) in dp:return dp[n,k]
            if k == 1:
                dp[n,k] = sum(A[:n])/float(n)
                return dp[n,k]
            dp[n,k] = 0
            for i in range(n-1,0,-1):
                a(i,k-1)
                dp[n,k] = max(dp[n,k],a(i,k-1) + sum(A[i:n])/float(n-i))
        a(len(A),K)
        return dp[len(A),K]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0]*(K+1) for _ in range(n+1)]
        
        for i in range(1, n+1):
            dp[i][1] = sum(A[:i])/i
        for i in range(2, n+1):
            for j in range(2, min(K+1, i+1)):
                dp[i][j] = max([dp[i-t][j-1] + sum(A[i-t:i]) / t for t in range(1,i)])
        return dp[n][K]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        mem = {}
        def dfs(l, K):
            if((l, K) in mem):
                return mem[(l, K)]
            if(l==len(A)):
                return 0
            if(K==1):
                return(sum(A[l:])/len(A[l:]))
            ans = sum(A[l:])/len(A[l:])
            for i in range(l+1, len(A)):
                avg = sum(A[l:i])/len(A[l:i])
                ans = max(ans, avg+dfs(i, K-1))
            mem[(l, K)]=ans
            return ans
        return dfs(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # i is starting index of array
        # return largest sum of averages for A[i:] using partitions
        def dfs(i, partitions):
            if partitions == 1:
                return (cum[len(A)]-cum[i-1])/(len(A)-i+1)
            mem[partitions][i] = 0
            for j in range(i, len(A)+1):
                if mem[partitions-1][j] == 0:
                    mem[partitions-1][j] = dfs(j, partitions-1)
                if j > i:
                    mem[partitions][i] = max(mem[partitions][i], mem[partitions-1][j] + (cum[j-1]-cum[i-1])/(j-i))
                else:
                    mem[partitions][i] = max(mem[partitions][i], mem[partitions-1][j])
            return mem[partitions][i]
                
        ans = 0
        cum = [0 for i in range(len(A)+1)]
        # mem[i][j] = i partitions from A[j]
        mem = [[0 for i in range(len(A)+1)] for j in range(K+1)]
        cum[0] = 0
        # cum[i] = sum of A[j] where j < i
        for i in range(len(A)):
            cum[i+1] = cum[i] + A[i]
        return dfs(1, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        from functools import lru_cache
        @lru_cache(None)
        def maxAverage(j, k):
            if j == k:
                return sum(A[:j])
            if k == 1:
                return sum(A[:j])/j
            ans = 0
            for i in range(j-1, max(-1,k-2), -1):
                ans = max(ans, (sum(A[i:j]))/(j-i) + maxAverage(i, k-1))
            return ans        
        return maxAverage(len(A), K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        N = len(A)
        pre_sum = [0 for i in range(N)]
        pre_sum[0] = A[0]
        
        for j in range(1, len(A)):
            
            pre_sum[j] = pre_sum[j-1] + A[j]
            
        dp = [[0 for n in range(N)] for k in range(K+1)]
        
        for i in range(N):
            
            dp[1][i] = pre_sum[i]/(i+1)
        
        for k in range(2, K+1):
            
            for i in range(N):
                
                for j in range(i):
                    
                    dp[k][i] = max(dp[k][i], pre_sum[i]/(i+1), dp[k-1][j] + (pre_sum[i] - pre_sum[j])/(i-j))
        
        return dp[K][N-1]
        


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        N = len(A)

        @lru_cache(None)
        def dfs(index, remain, acc, size):
            if index >= N:
                return 0 if size == 0 else acc / size
            ans = 0
            if remain > 0:
                ans = max(ans, (acc + A[index]) / (size + 1) + dfs(index + 1, remain - 1, 0, 0))
            ans = max(ans, dfs(index + 1, remain, acc + A[index], size + 1))
            return ans

        return dfs(0, K - 1, 0, 0)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        if K >= n: return sum(A)
        
        B = [0] * (n+1)
        B[1] = A[0]
        for i in range(1, n):
            B[i+1] = B[i] + A[i]
        
        maxSum = 0
        
        @lru_cache(None)
        def dp(si, ei, remainK):
            if ei == n:
                return (B[ei] - B[si]) / (ei - si)
            tmp = 0 
            if remainK > 1:
                tmp = max(tmp, (B[ei] - B[si]) / (ei - si) + dp(ei, ei+1, remainK - 1))
                
            tmp = max(tmp, dp(si, ei+1, remainK))
            return tmp
            
        #maxSum = max(maxSum, dp(ovr_))
        maxSum = dp(0, 1, K)
        print(maxSum)
        
        return maxSum

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        
        def average(i, j):
            return (P[j] - P[i]) / float(j-i)
        
        N = len(A)
        dp = [average(i, N) for i in range(N)]
        for k in range(K-1):
            for i in range(N):
                for j in range(i+1, N):
                    dp[i] = max(dp[i], average(i, j) + dp[j])
        
        return dp[0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        L = len(A)
        dp = [
            [0 for _ in range(K + 1)] for _out in range(L)
        ]
        
        dp[0][1] = A[0]
        for i in range(1, L):
            dp[i][1] = (dp[i - 1][1] * i + A[i]) / (i + 1)
        # for i in dp:
        #     print(i)
            
        for i in range(1, L):
            for k in range(2, K + 1):
                if k > i + 1:
                    dp[i][k] = dp[i][k - 1]
                else:
                    for j in range(-1, i):
                        subarr = A[j + 1 : i + 1]
                        # print(j, i, subarr)
                        ave = sum(subarr) / len(subarr)
                        if j == -1:
                            tmp = 0
                        else:
                            tmp = dp[j][k - 1]
                        # print(ave, tmp)
                        if ave + tmp > dp[i][k]:
                            dp[i][k] = ave + tmp
        # for i in dp:
        #     print(i)
        # print('done')
        return dp[-1][-1]

class Solution:
    def solve(self, start_index, num_groups):
        if (start_index, num_groups) in self.memo:
            return self.memo[(start_index, num_groups)]
        
        if start_index == 0:
            sum_up_to = 0
        else:
            sum_up_to = self.sums[start_index - 1]
        
        if num_groups == 1:
            res = (self.sums[-1] - sum_up_to) / (self.N - start_index)
        else:
            res = 0
            num_remaining_groups = num_groups - 1
            for start_next_group in range(start_index + 1, self.N - num_remaining_groups + 1):
                group_avg = (self.sums[start_next_group - 1] - sum_up_to) / (start_next_group - start_index)
                res = max(res, group_avg + self.solve(start_next_group, num_groups - 1))
                pass
        
        self.memo[(start_index, num_groups)] = res
        return res
    
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        self.memo = {} # start index, K -> result
        
        self.N = len(A)
        self.sums = [None] * len(A)
        self.sums[0] = A[0]
        for i in range(1, len(A)):
            self.sums[i] = self.sums[i - 1] + A[i]
        
        r = self.solve(0, K)
        print(self.memo)
        return r

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        self.dp = {}
        self.arr = A
        ans = self.helper(0,K-1)
        #print(self.dp)
        return ans
        
    
    def helper(self,i,k):
        if(k == 0):
            return sum(self.arr[i:])/len(self.arr[i:])
        if(i == len(self.arr)-1):
            return -10**100
        
        if((i,k) in self.dp):
            return self.dp[(i,k)]
        
        ans = 0
        for j in range(i,len(self.arr)-1):
            tmp = sum(self.arr[i:j+1])/(len(self.arr[i:j+1])) + self.helper(j+1, k-1)
            ans = max(ans, tmp)
        self.dp[(i,k)] = ans
        return self.dp[(i,k)]


class Solution:
    def part(self, A, i, K, cache):
        if i < 0:
            if K == 0:
                return 0
            return float('-Inf')
        if i == 0:
            if K != 1:
                return float('-Inf')
            return A[i]
        key = '{}-{}'.format(i, K)
        if key in cache:
            return cache[key]
        res = float('-Inf')
        sm = 0
        count = 0
        for j in range(i, -1, -1):
            sm += A[j]
            count += 1
            avg = float(sm) / float(count)
            res = max(res, avg + self.part(A, j-1, K-1, cache))
        cache[key] = res
        return res
    
    def solve(self, A, K):
        return self.part(A, len(A)-1, K, {})
    
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        return self.solve(A, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        if K >= n: return sum(A)
        
        B = [0] * (n+1)
        B[1] = A[0]
        for i in range(1, n):
            B[i+1] = B[i] + A[i]
        
        @lru_cache(None)
        def dp(si, ei, remainK):
            if ei == n:
                return (B[ei] - B[si]) / (ei - si)
            tmp = 0 
            if remainK > 1:
                tmp = max(tmp, (B[ei] - B[si]) / (ei - si) + dp(ei, ei+1, remainK - 1))
                
            tmp = max(tmp, dp(si, ei+1, remainK))
            return tmp
        
        return dp(0, 1, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], k: int) -> float:
        n=len(A)
        mtr=[[0 for i in range(n+1)] for j in range(k+1)]
        # mtr[k][n]
    
        
       
        # RECURSIVE START
        def rec(parts,arrIndex):
            # print(parts,arrIndex)
            if mtr[parts][arrIndex]!=0:
                return mtr[parts][arrIndex]
            
            if parts==1:
                mtr[parts][arrIndex]=sum(A[:arrIndex+1])/(arrIndex+1)
                return mtr[parts][arrIndex]
            
            for x in range(1,arrIndex+1):
                mtr[parts][arrIndex]=max(mtr[parts][arrIndex],rec(parts-1,x-1)+sum(A[x:arrIndex+1])/(arrIndex+1-x))
            return mtr[parts][arrIndex]
        
        rec(k,n-1)
        # RECURSIVE END

        
        
        # ITERATIVE START
        # for i in range(n):
        #     mtr[1][i]=sum(A[:i+1])/(i+1)    
        # for i in range(2,k+1):
        #     for j in range(n):
        #         for x in range(j+1):
        #             # print(\"(\",mtr[i-1][x],\",\",x,\")\",mtr[i-1][x]+(sum(A[x:j])/(j-x)),i,x,j)
        #             mtr[i][j] = max(mtr[i][j],mtr[i-1][x-1]+(sum(A[x:j+1])/(j+1-x)))
        # ITERATIVE END



#         for i in mtr:
#             print(i)
        
        ans=sys.maxsize *(-1)
        for i in range(1,k+1):
            ans=max(ans,mtr[i][-2])
        return ans


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        self.memo = {}       
        def helper(start,end,K,prefix):
            if (start,end,K) in self.memo.keys():
                return self.memo[(start,end,K)]
            
            if K == 0: return (prefix[end+1] - prefix[start])/(end-start+1)
            
            if end == start: return prefix[end+1] - prefix[end]
            if end < start : return 0 
            
            maxAvg = 0
            for i in range(start,end):
                maxAvg = max(maxAvg,(prefix[i+1]-prefix[start])/(i-start+1) + helper(i+1,end,K-1,prefix))
            self.memo[(start,end,K)] = maxAvg
            return maxAvg
            
        
        n = len(A)
        prefix = [ 0 for _ in range(n+1)]
        for i in range(1,n+1):
            prefix[i] = prefix[i-1] + A[i-1]            
        
        ans = 0
        for k in range(K):
            ans = max(ans, helper(0,n-1,k,prefix))
            
            
        return ans

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0] * n for _ in range(K)] 
        # dp: K*n, dp[k][i]: result for largestSum of first (i+1) elements with k+1 groups
        for i in range(n):
            dp[0][i] = sum(A[:(i+1)]) / (i+1)
        for l in range(1, K):
            for i in range(l, n):
                for j in range(i):
                    dp[l][i] = max(dp[l][i], dp[l-1][j] + sum(A[j+1:i+1])/(i-j))
        return dp[K-1][n-1]        

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0] * n for _ in range(K)] 
        # dp: K*n, dp[k][i]: result for largestSum of first (i+1) elements with k+1 groups
        for i in range(n):
            dp[0][i] = sum(A[:(i+1)]) / (i+1)
        for l in range(1, K):
            for i in range(l, n):
                for j in range(i):
                    dp[l][i] = max(dp[l][i], dp[l-1][j] + sum(A[j+1:i+1])/(i-j))
        print(dp)
        return dp[K-1][n-1]        

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        len_A = len(A)
        dp = [[0 if j else sum(A[:i + 1]) / (i + 1) for j in range(K)] for i in range(len_A)]
        for i in range(len_A):
            for j in range(1, K):
                if j > i:
                    break
                for k in range(i):
                    dp[i][j] = max(dp[i][j], dp[k][j - 1] + sum(A[k + 1:i + 1]) / (i - k))
        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # dynamic programming, O(NKN) time, O(NK) space
        avg = lambda arr: sum(arr) / len(arr)        
        n = len(A)
        dp = [[0] * K for _ in range(n)]
        for i in range(n):
            for k in range(K):
                if k == 0:
                    dp[i][k] = avg(A[:i+1])
                else:
                    if len(A[:i+1]) < k+1:
                        break
                    for j in range(i):
                        dp[i][k] = max(dp[j][k-1] + avg(A[j+1:i+1]), dp[i][k])
        print(dp)
        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        n = len(A)
        dp = [[0 for k in range(K)] for i in range(n)]
        for k in range(K):
            dp[0][k] = A[0]
        for i in range(1, n):
            dp[i][0] = dp[i-1][0] * i / (i+1) + A[i] / (i+1)
        for k in range(1, K):
            for i in range(1, n):
                dp[i][k] = dp[i][k-1]
                for j in range(i):
                    dp[i][k] = max(dp[i][k], dp[j][k-1] + sum(A[j+1:i+1])/(i-j))
        return dp[n-1][K-1]
                
        
        
        
        
        
        
        
        
        
#         memo = [[0 for k in range(K)] for i in range(n)]
        
#         def aux(A, cur, k, memo):
#             if cur == len(A):
#                 return 0
#             if memo[cur][k]:
#                 return memo[cur][k]
#             tmp = sum(A[cur:])/(len(A)-cur)
#             if k == 0:
#                 memo[cur][k] = tmp
#                 return tmp
#             for i in range(cur+1, len(A)+1):
#                 tmp = max(tmp, sum(A[cur:i])/(i-cur) + aux(A, i, k-1, memo))
#             memo[cur][k] = tmp
#             return tmp
                
#         return aux(A, 0, K-1, memo)
        
        
        


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        n = len(A)
        dp = [[0 for k in range(K)] for i in range(n)]
        for k in range(K):
            dp[0][k] = A[0]
        for i in range(1, n):
            dp[i][0] = dp[i-1][0] * i / (i+1) + A[i] / (i+1)
        for k in range(1, K):
            for i in range(1, n):
                for j in range(i):
                    dp[i][k] = max(dp[i][k], dp[j][k-1] + sum(A[j+1:i+1])/(i-j))
        return dp[n-1][K-1]
                
        
        
        
        
        
        
        
        
        
#         memo = [[0 for k in range(K)] for i in range(n)]
        
#         def aux(A, cur, k, memo):
#             if cur == len(A):
#                 return 0
#             if memo[cur][k]:
#                 return memo[cur][k]
#             tmp = sum(A[cur:])/(len(A)-cur)
#             if k == 0:
#                 memo[cur][k] = tmp
#                 return tmp
#             for i in range(cur+1, len(A)+1):
#                 tmp = max(tmp, sum(A[cur:i])/(i-cur) + aux(A, i, k-1, memo))
#             memo[cur][k] = tmp
#             return tmp
                
#         return aux(A, 0, K-1, memo)
        
        
        


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        p = [0]
        for i in range(n):
            p.append(p[i]+A[i])
        def average(i,j):
            return (p[j]-p[i]) / (j-i)
        dp = [[0]*n for _ in range(K)]
        for i in range(n):
            dp[0][i] = average(i,n)            
            

        for k in range(1, K):
            for i in range(n):
                for j in range(i+1, n):
                    dp[k][i] = max(dp[k][i], average(i,j)+dp[k-1][j])
        return dp[K-1][0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # dynamic programming, 
        avg = lambda arr: sum(arr) / len(arr)        
        n = len(A)
        dp = [[0] * K for _ in range(n)]
        for i in range(n):
            for k in range(K):
                if k == 0:
                    dp[i][k] = avg(A[:i+1])
                else:
                    if len(A[:i+1]) < k+1:
                        break
                    for j in range(i):
                        dp[i][k] = max(dp[j][k-1] + avg(A[j+1:i+1]), dp[i][k])
        print(dp)
        return dp[-1][-1]

class Solution:
    def mean(self, l):
        return sum(l)/len(l)
    
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        DP = [self.mean(A[i:n]) for i in range(n)]
        
        for k in range(K-1):
            for i in range(n):
                for j in range(i+1, n):
                    DP[i] = max(DP[i], self.mean(A[i:j]) + DP[j])

        return DP[0]
        
        
        
        
#         n = len(A)
#         if n==1:
#             return A[0]
#         if K==1:
#             return self.mean(A)
#         DP = {}
        
#         for i in range(1, n-K+2):
#             if i>n-1:
#                 break
#             if K==2:
#                 DP[i] = self.mean(A[:i]) + self.mean(A[i:])
#             else:
#                 DP[i] = self.mean(A[:i]) + self.largestSumOfAverages(A[i:], K-1)
#         return max(list(DP.values()))



class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        sums = [0 for i in range(n+1)]
        dp = [[0 for i in range(n+1)] for k in range(K+1)]
        
        for i in range(1, n+1):
            sums[i] += sums[i-1] + A[i-1]
        
        for i in range(1,n+1):
            dp[1][i] = sums[i] / i
        
        for k in range(2, K+1):
            for i in range(n+1):
                for j in range(i):
                    dp[k][i] = max(dp[k][i], dp[k-1][j] + (sums[i] - sums[j]) / (i-j))
        return dp[K][n]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        def avg(array):
            return sum(array) / len(array)
        dp = [[0 for _ in range(K)] for _ in range(len(A))]
        dp[0][0] = A[0]
        for i in range(len(A)):
            for j in range(K):
 #               if i == 0 and j != 0:
 #                  continue
                if j == 0:
                    dp[i][j] = avg(A[:i+1])
                else:
                    for k in range(i):
                        dp[i][j] = max(dp[i][j],dp[k][j-1]+avg(A[k+1:i+1]))
        return dp[len(A)-1][K-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        self.arr = [[None for i in range(K)] for i in range(len(A))]
        res = self.solve(A, 0, K, -1)
        #print(self.arr)
        return res
    
    
    def solve(self, arr, i, grpLeft, lastInd):
        if i == len(arr):
            return 0

        if self.arr[lastInd+1][grpLeft-1] != None:
            return self.arr[lastInd+1][grpLeft-1]
        
        if grpLeft == 1:
            self.arr[lastInd+1][0] = sum(arr[lastInd+1:])/(len(arr)-lastInd-1)
            return self.arr[i][0]
        
        avg = float(sum(arr[lastInd+1:i+1]))/(i-lastInd)
     
        self.arr[lastInd+1][grpLeft-1] = max(self.solve(arr, i+1, grpLeft, lastInd), avg + self.solve(arr, i+1, grpLeft-1, i))
        return self.arr[lastInd+1][grpLeft-1]



class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0]*(K+1) for i in range(n)]
        total = [A[0]]
        for i in range(1, n):
            total.append(A[i] + total[i-1])
        def solve(start, k):
            if dp[start][k] != 0:
                return dp[start][k]
            
            if k == 1:
                dp[start][k] = (total[n-1] - total[start] + A[start])/(n-start)
                return dp[start][k]
            
            i = start
            while i + k <= n:
                temp = (total[i] - total[start] + A[start])/(i-start+1) + solve(i+1, k-1)
                dp[start][k] = max(dp[start][k], temp)
                i += 1
            return dp[start][k]
        
        return solve(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], k: int) -> float:
        n=len(A)
        mtr=[[0 for i in range(n+1)] for j in range(k+1)]
        # mtr[k][n]
        for i in range(n):
            mtr[1][i]=sum(A[:i+1])/(i+1)
        for i in range(2,k+1):
            for j in range(n):
                for x in range(j+1):
                    # print(\"(\",mtr[i-1][x],\",\",x,\")\",mtr[i-1][x]+(sum(A[x:j])/(j-x)),i,x,j)
                    mtr[i][j] = max(mtr[i][j],mtr[i-1][x-1]+(sum(A[x:j+1])/(j+1-x)))
        # for i in mtr:
        #     print(i)
        
        ans=sys.maxsize *(-1)
        for i in range(1,k+1):
            ans=max(ans,mtr[i][-2])
        return ans


class Solution:
    def largestSumOfAverages(self, A: List[int], k: int) -> float:
        n=len(A)
        mtr=[[0 for i in range(n+1)] for j in range(k+1)]
        # mtr[k][n]
        # for i in range(n):
        #     mtr[1][i]=sum(A[:i+1])/(i+1)
        
       
            
        def rec(parts,arrIndex):
            # print(parts,arrIndex)
            if mtr[parts][arrIndex]!=0:
                return mtr[parts][arrIndex]
            
            if parts==1:
                mtr[parts][arrIndex]=sum(A[:arrIndex+1])/(arrIndex+1)
                return mtr[parts][arrIndex]
            
            for x in range(1,arrIndex+1):
                mtr[parts][arrIndex]=max(mtr[parts][arrIndex],rec(parts-1,x-1)+sum(A[x:arrIndex+1])/(arrIndex+1-x))
            return mtr[parts][arrIndex]
        
        rec(k,n-1)
        
        
#         for i in range(2,k+1):
#             for j in range(n):
#                 for x in range(j+1):
#                     # print(\"(\",mtr[i-1][x],\",\",x,\")\",mtr[i-1][x]+(sum(A[x:j])/(j-x)),i,x,j)
#                     mtr[i][j] = max(mtr[i][j],mtr[i-1][x-1]+(sum(A[x:j+1])/(j+1-x)))
        for i in mtr:
            print(i)
        
        ans=sys.maxsize *(-1)
        for i in range(1,k+1):
            ans=max(ans,mtr[i][-2])
        return ans


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        dp=[[0 for j in range(K)] for i in A]
        for j in range(len(A)):
            for i in range(K): 
                if i==0:
                    dp[j][i]=sum(A[:j+1])/len(A[:j+1])
                else:
                    if len(A[:j+1])<i+1:
                        break
                    for k in range(j):
                        dp[j][i]=max(dp[k][i-1]+sum(A[k+1:j+1])/len(A[k+1:j+1]), dp[j][i])
        return dp[-1][-1]


class Solution():
    def largestSumOfAverages(self, A, K: int) -> float:
        dp = []
        for i in range(len(A)):
            tmp = []
            for j in range(1, 1 + K):
                tmp.append(0)
            dp.append(tmp)
        v = 0
        for i in range(len(dp)):
            v += A[i]
            for j in range(len(dp[0])):
                if j == 0:
                    dp[i][j] = v / (i+1)
                elif j == i:
                    dp[i][j] = v
        for i in range(len(dp)):
            for j in range(1,min(i,K)):
                for t in range(i):
                    dp[i][j] = max(dp[i][j],dp[t][j-1]+self.avg(A[t+1:i+1]))
        return dp[-1][-1]

    def avg(self,nums):
        return sum(nums) / len(nums)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        accsum = A[:]
        l = len(accsum)
        for i in range(1, l):
            accsum[i] += accsum[i-1]
        
        cache = {}
        def dp(i, k):
            prev = accsum[i-1] if i>0 else 0
            
            if k == 1:
                res = (accsum[l-1]-prev)/(l-i)
                cache[(i,k)] = res
                return res

            if (i,k) in cache:
                return cache[(i, k)]
            if l-i < k:
                return -float('inf')
            if l-i == k:
                res = accsum[l-1]-prev
                cache[(i,k)] = res
                return res
            
            res = 0
            for j in range(i, l-k+1):
                res = max(res, (accsum[j]-prev)/(j-i+1) + dp(j+1, k-1))
            cache[(i, k)] = res
            return res
    
        return dp(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        dp = [[0 for j in range(K)] for i in A]
        for j in range(len(A)):
            for i in range(K):
                if i==0:
                    dp[j][i] = sum(A[:j+1])/len(A[:j+1])
                else:
                    if len(A[:j+1]) < i+1:
                        break
                    for k in range(j):
                        dp[j][i]=max(dp[k][i-1]+sum(A[k+1:j+1])/len(A[k+1:j+1]),dp[j][i])
        return dp[-1][-1]
                    


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

        def fn(nums, k):
            if len(nums) <= k:
                return sum(nums)
            elif k == 1:
                return sum(nums) / len(nums)
            else:
                max_avg = 0
                for i in reversed(range(len(nums))):
                    key = (tuple([num for num in nums[:i]]), k-1)
                    if key not in memo:
                        memo[key] = fn([num for num in nums[:i]], k-1)
                    avg = memo[key] + sum(nums[i:]) / (len(nums) - i)
                    max_avg = max(max_avg, avg)
                return max_avg

        return fn(A, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        averages = [[None for _ in range(n)] for _ in range(n)]
        for i in range(n):
            averages[i][i] = A[i]
        for i in range(n-1):
            for j in range(i+1, n):
                averages[i][j] = (averages[i][j-1] * (j - i) + A[j]) / (j - i + 1)
        dp = [[None for _ in range(K)] for _ in range(n+1)]
        def largestSum(i, count):
            if dp[i][count] != None:
                return dp[i][count]
            if i == n:
                dp[i][count] = 0
                return 0
            if count == K - 1:
                dp[i][count] = averages[i][n-1]
                return averages[i][n-1]
            largest = float('-inf')
            for k in range(n):
                largest = max(largest, averages[i][min(i+k,n-1)] + largestSum(min(i+k+1,n), count+1))
            dp[i][count] = largest
            return largest
        return largestSum(0, 0)
                


class Solution:
    def largestSumOfAverages(self, A, K):
    
        dp=[[0 for j in range(K)] for i in A]
    
     
        for j in range(len(A)):
            for i in range(K): 
                if i==0:
                    dp[j][i]=sum(A[:j+1])/len(A[:j+1])
                else:
                    if len(A[:j+1])<i+1:
                        break
                    for k in range(j):
                    
                        dp[j][i]=max(dp[k][i-1]+sum(A[k+1:j+1])/len(A[k+1:j+1]),dp[j][i])
                    

        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        @lru_cache(None)
        def helper(i,t):
            if(i>=len(A)):
                return 0
            if(t==K-1):
                return sum(A[i:])/(len(A)-i)
            else:
                m=-1
                for j in range(1,len(A)):
                    m=max(m,helper(i+j,t+1)+sum(A[i:i+j])/j) 
                    if(t==3):
                        print(m)
                return m
        return helper(0,0)

class Solution:
    def largestSumOfAverages(self, a: List[int], k: int) -> float:
        def rec(st, k):
            if (st, k) in cache:
                return cache[(st, k)]
            if k == 1:
                cache[(st, k)] = sum(a[st:])/(len(a)-st)
                return cache[(st, k)]
            total = 0
            res = -math.inf
            for i in range(st, len(a)-k+1):
                total += a[i]
                res = max(res, (total/(i-st+1)) + rec(i+1, k-1))
            cache[(st, k)] = res
            return cache[(st, k)]
        cache = {}
        return rec(0, k)


def find(dp,start,end,k,arr):
    if start > end:
        return -float('inf')
    if k <= 0:
        return -float('inf')
    if (start,end,k) in dp.keys():
        return dp[(start,end,k)]

    if start == end:
        if k == 1:
            return arr[start]
        return 0
    
    ans = 0
    total = 0
    count = 0
    for i in range(start,end+1):
        total += arr[i]
        count += 1
        if k-1 > 0:
            find(dp,i+1,end,k-1,arr)
            ans = max(ans,(total/count)+find(dp,i+1,end,k-1,arr))

    ans = max(ans,total/count)
    dp[(start,end,k)] = ans

    return ans

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        dp = {}
        return find(dp,0,len(A)-1,K,A)

class Solution:
    def largestSumOfAverages(self, A: List[int], k: int) -> float:
          n=len(A)
          pre= list(itertools.accumulate([0]+A))
          dp={}
          def dfs(i,k):
             if (i,k) in dp:
                    return dp[(i,k)]
             if k==1:
                    dp[(i,k)]=(pre[-1]-pre[i])/(n-i)
                    return dp[(i,k)]
             ans=-float('inf');cur=0
             for j in range(i,n-k+1):
                  ans=max(ans,(pre[j+1]-pre[i])/(j-i+1)+dfs(j+1,k-1))
             dp[(i,k)]=ans
             return ans
          return dfs(0,k)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        #if not A: return 0
        #if len(A)==1: return A[0]
        # Real Run Time is a little bit UNSTABLE
        N = len(A)
        P = [0] * (N+1)
        for i in range(1,N+1): P[i] = P[i-1] + A[i-1] # 注： cumulative sum of A[:i]
        
        # Table[a] = optimal for A[a:] with k subsets, initially k=1
        Table = [(P[N]-P[i])/(N-i) for i in range(N)]
        for k in range(2, K+1): # 注： starting from k=2 subsets, end at k=K subsets at most
            # 注： optimal for A[i:] with k subsets means: optimal pair{ 1 subset A[i:j] and optimal A[j:] with (k-1) subsets whose value saved in Table[j], where i+1=<j<=N-(k-1)}
            for i in range(K-k,N-(k-1)): # 注： 
                Table[i] = max((P[j]-P[i])/(j-i) + Table[j] for j in range(i+1,N-(k-1)+1))
        
        return Table[0]   

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        @lru_cache(None)
        def dp(n,k):
            if n<k:
                return 0
            if k==1:
                return sum(A[:n])/n
            cur, ans = 0,0
            for i in range(n-1,0,-1):
                cur+=A[i]
                ans =max(ans, dp(i, k-1)+ cur/(n-i))
            return ans
        return dp(len(A),K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = {}
        def f(i, k):
            if (i, k) not in dp:
                if k == 1:
                    dp[(i, k)] = sum(A[i:])/(n - i)
                else:
                    dp[(i, k)] = max([(sum(A[i:j])/(j - i) + f(j, k - 1)) for j in range(i + 1, n - k + 2)])
            return dp[(i, k)]
        return f(0, K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [0] * (n + 1)
        sums = [0] * (n + 1)
        for i in range(1, n + 1):
            sums[i] = sums[i - 1] + A[i - 1]
            dp[i] = sums[i] / i
            
        for k in range(2, K + 1):
            tmp = [0] * (n + 1)
            for i in range(k, n + 1):
                for j in range(k - 1, i):
                    tmp[i] = max(tmp[i], dp[j] + (sums[i] - sums[j]) / (i - j))
            dp = list(tmp)
        
        return dp[n]
                    
                    


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if K == 1:
            return sum(A)/(len(A))
        
        memo = [[0]*len(A) for _ in range(K)]
        cumsum = [0]*len(A)
        
        for i in range(len(A)):
            cumsum[i] = cumsum[i-1] + A[i]
            memo[0][i] = cumsum[i]/(i+1)
        
        for i in range(1,K):
            for j in range(i,len(A)):
                tmp = 0
                for k in range(i-1,j):
                    tmp = max(tmp, memo[i-1][k] +(cumsum[j]-cumsum[k])/(j-k))
                    
                memo[i][j] = tmp
        
        return memo[-1][-1]


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        dp = [[0.0 for j in range(K + 1)] for i in range(len(A))]
        sums = [0] * len(A)
        sums[0] = A[0]
        for i in range(1, len(A)):
            sums[i] = sums[i - 1] + A[i]

        for k in range(1, K + 1):
            for i in range(len(A)):
                if k == 1:
                    dp[i][k] = sums[i] / (i + 1)
                elif k > i + 1:
                    continue
                else:
                    for j in range(k - 1, i + 1):
                        avg1 = dp[j - 1][k - 1]
                        avg2 = (sums[i] - sums[j - 1]) / (i - j + 1)
                        if dp[i][k] < avg1 + avg2:
                            dp[i][k] = avg1 + avg2

        return dp[-1][K]

from functools import lru_cache

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # K <= A <= 100
        # O((AK)^2) could work
        # Looks like dp
        
        @lru_cache(None)
        def rec(j,K):
            nonlocal A
            
            if K == 1:
                return sum(A[0:j+1])/(j+1)
            
            res = 0
            runningsum = 0
            for i in range(j, K-2, -1):
                runningsum += A[i]
                res = max(res, runningsum/(j - i + 1) + rec(i-1,K-1))
            return res
        
        return rec(len(A)-1, K)
            
        
        


import functools
class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        @functools.lru_cache(None)
        def dp(start,p):
            if p==1:
                return sum(A[start:])/(len(A)-start)
            if start==len(A):
                return 0
            curr_sum=A[start]
            ret=0
            for i in range(start+1,len(A)):
                avg=curr_sum/(i-start)
                ret=max(ret,avg+dp(i,p-1))
                curr_sum+=A[i]
            return ret
        return dp(0,K)
            


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        N = len(A)
        P = [0]
        for a in A:
            P.append(P[-1]+a)

        dp = [0]*(N+1)
        for i in range(K):
            dp2 = [0]*(N+1)
            for j in range(i, N+1):
                if i==0 and j!=0:
                    dp2[j] = P[j]/j
                    continue
                    
                for k in range(i-1, j):
                    dp2[j] = max(dp2[j], dp[k]+(P[j]-P[k])/(j-k))
            
            dp = dp2
        return dp[-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        num_count     = len(A)
        previous_best = [0]*num_count # best average sums for the previous number of partitions
        current_best  = [0]*num_count # best average sums for the current number of partitions
        
        previous_best[0] = A[0] 
        for index in range(1, num_count):
            A[index] += A[index - 1]
            previous_best[index] = A[index] / (index + 1)
        
        for partition_count in range(1, K):
            for end_index in range(partition_count, num_count - K + partition_count + 1):
                
                current_best[end_index] = max(
                    (A[end_index] - A[start_index]) / (end_index - start_index)  + previous_best[start_index] 
                    for start_index in range(partition_count - 1, end_index)
                )
            current_best, previous_best = previous_best, current_best
        return previous_best[-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        memoDict = {}
        def recurse(i,k):
            #print(i,k)
            n = len(A)
            max_win = n-i - (k-1)
            if (i,k) in memoDict:
                return memoDict[(i,k)] 
            if k == 0:
                return sum(A[i:])/(n-i)
            else:
                max_sum = 0
                for ind in range(1,max_win):
                    lul = recurse(i+ind,k-1)+sum(A[i:i+ind])/(ind)
                    max_sum = max(max_sum,lul)
                    #print(A[i:i+ind],A[i+ind:],lul,k)
                memoDict[(i,k)] = max_sum   
                return max_sum
        flips = recurse(0,K-1)
        #print(memoDict)
        return flips 

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        from functools import lru_cache
        @lru_cache(None)
        def dp(i,j):
            if i == n:
                return float('-inf')
            if j == 1:
                return sum(A[i:]) / (n-i)
            ans = float('-inf')
            cur_sum = 0
            for l in range(i, n):
                cur_sum += A[l]
                ans = max(ans, cur_sum / (l-i+1) + dp(l+1, j-1))
            return ans;
        return dp(0, K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefix_sum = [A[0]]
        for a in A[1:]:
            prefix_sum.append(prefix_sum[-1] + a)
        dp = [[0 for _ in range(len(A))] for _ in range(K)]
        for i in range(len(A)):
            dp[0][i] = prefix_sum[i] / (i + 1)
        for k in range(1, K):
            for i in range(k, len(A)):
                for j in range(k - 1, i):
                    dp[k][i] = max(dp[k][i], dp[k - 1][j] + (prefix_sum[i] - prefix_sum[j]) / (i - j))
        return dp[K - 1][len(A) - 1]
        # dp[i][j] => result for i+1 groups, j idx in A
        # dp[i][j] = max(dp[i-1][k] + avg(A[k+1:j]) for k = 0..j-1)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0] * K for _ in range(n)]
        dp[0][0] = A[0]
        for i in range(1, n):
            dp[i][0] = (dp[i-1][0] * i + A[i]) / (i + 1)

        for k in range(1, K):
            for i in range(k, n):
                curr_sum = 0
                for j in reversed(range(k, i+1)):
                    curr_sum += A[j]
                    dp[i][k] = max(dp[i][k], dp[j-1][k-1] + curr_sum / (i+1 - j))
        return dp[n-1][K-1]

class Solution(object):
    def largestSumOfAverages(self, A, K):
        memo = {}
        def search(n, k):
            if (n, k) in memo: 
                return memo[n, k]
            if n < k: 
                return 0
            if k == 1:
                memo[n, k] = sum(A[:n]) / float(n)
                return memo[n, k]
            cur = 0
            res = 0
            for i in range(n - 1, 0, -1):
                cur += A[i]
                res = max(res, search(i, k - 1) + cur / float(n - i))
            memo[n, k] = res
            return memo[n, k]
        return search(len(A), K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if not A:
            return 0
        n = len(A)
        # Pre compute sums
        sums = [0] * (n + 1)
        # dp[k][i] stands for the answer of first i elements divided into k groups
        dp = [[float('-inf')] * (n + 1) for _ in range(K + 1)]
        for i in range(1, n + 1):
            sums[i] = sums[i - 1] + A[i - 1]
            dp[1][i] = sums[i] / i
        for k in range(2, K + 1):
            for i in range(k, n + 1):
                # Break point j from k - 1 till i
                for j in range(k - 1, i):
                    ave_i_j = (sums[i] - sums[j]) / (i - j)
                    dp[k][i] = max(dp[k][i], dp[k - 1][j] + ave_i_j)
        return dp[K][n]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if not A:
            return 0
        elif len(A) <= K:
            return sum(A)
        size = len(A)
        dp = [[0] * (size + 1) for _ in range(K + 1)]
        preSum = [sum(A[:i]) for i in range(size + 1)]
        for j in range(size):
            dp[1][j + 1] = (preSum[j + 1]) / (j + 1)
        for k in range(2, K + 1):
            for i in range(k, size + 1):
                for j in range(i, k - 1, -1):
                    dp[k][i] = max(dp[k][i], dp[k - 1][j - 1] + (preSum[i] - preSum[j - 1]) / (i - j + 1))
        print(dp)
        return max([dp[i][size] for i in range(1, K + 1)])

# A[1~N] K (1 <= K <= N)
# 
# B[m][w] = 前A[1~m]分w組的最大平均值總和
# 
# B[m][w] = max(B[m-1][w-1] + A[m]
#               B[m-2][w-1] + (A[m-1]+A[m])/2
#               B[m-3][w-1] + (A[m-2 ~ m])/3

class Solution:
  def largestSumOfAverages(self, A, K):
    N = len(A)
    S = [0] * (1 + N)
    for i in range(1, N + 1):
        S[i] = S[i - 1] + A[i - 1]
    B = []
    for i in range(1 + N):
      B.append([0] * (1 + K))
    for m in range(1, N + 1):     # m : 剩餘人數
        for w in range(1, K + 1): # w : 剩餘組數
            if w == 1:
                B[m][w] = S[m] / m
                continue
            if m < w:
                break
            B[m][w] = -1000000
            for e in range(1, m - w + 2): # e : 最後一組的人數
                B[m][w] = max(B[m][w], B[m - e][w - 1] +
                                       (S[m] - S[m - e]) / e)
            # print('B[%d][%d] = %f' % (m, w, B[m][w]))
    return B[N][K]


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
      
        n=len(A)
        dp=[[0]*(K+1) for _ in range(n)]
        s=0
        for i in range(n):
            s+=A[i]
            dp[i][1]=s*1.0/(i+1)
        
        for k in range(2,K+1):
            for i in range(k-1,n):
                s=0
                for m in range(i,k-2,-1):
                    s+=A[m]
                    dp[i][k]=max(dp[i][k],dp[m-1][k-1]+s*1.0/(i-m+1))
        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        cumsum = [A[0]]
        for i in range(1, len(A)):
            cumsum.append(cumsum[-1] + A[i])
        cumsum.append(0)

        @lru_cache(None)
        def rec(i, K):
            if K == 1:
                return (cumsum[len(A)-1] - cumsum[i-1]) / (len(A)-i)
            return max((cumsum[j] - cumsum[i-1]) / (j-i+1) + rec(j+1, K-1) for j in range(i, len(A)-K+1))

        return rec(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        #larger sum in subarray group 往dp想，一般都是第一类区间dp
        #这类区间的套路就是dp[i][k] 前i个分成k个group的最优解
        #转移方程
  #      for (i=1; i<=N; i++)
  #         for (k=1; k<=min(i,K); k++)
  #     // find the best break point j （jd的区间就是i - k, c从高到低）
  #             for (int j=i; j>=k; j--)
  #                 dp[i][k] = max(dp[i][k], dp[j-1][k-1] + sum[j:i] );


        n = len(A)
        A = [0] + A
        dp = [[0]*(K+1) for _ in range(n+1)]
        
        for i in range(1, n+1):
             dp[i][0] = -float('inf')
        
        for i in range(1, n+1):
            for k in range(1, min(i+1, K+1)):
                sum_s = 0
                #这里j要从最大的往回走，才能统计sum
                for j in range(i, k-1, -1):
                    sum_s += A[j]
                    dp[i][k] = max(dp[i][k], dp[j-1][k-1] + sum_s/(i-j + 1))
        
        res = 0 
        for i in range(1, K+1):
            res = max(res, dp[n][i])
        
        return res







  # 
#         n = len(A)
#         dp = [[0]*(K+1) for _ in range(n+1)]
        
#         A = [0] + A
        
#         for i in range(1, n+1):
#             dp[i][0] = -float('inf')
        
#         for i in range(1, n+1):
#             for k in range(1, min(K+1, i+1)):
#                 #
#                 sum_s = 0
#                 for j in range(k, i+1):
#                     sum_s += A[j]
#                     dp[i][k] = max(dp[i][k], dp[j-1][k-1] + sum_s//(i-j+1) )
        
#         res = 0
#         for i in range(1, K+1):
#             res = max(res, dp[n][i])
#         print(dp)
#         return res
     
    
    


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if not A:
            return 0
        elif len(A) <= K:
            return sum(A)
        size = len(A)
        dp = [[0] * (size + 1) for _ in range(K + 1)]
        for j in range(size):
            dp[1][j + 1] = sum(A[:j + 1]) / (j + 1)
        for k in range(2, K + 1):
            for i in range(k, size + 1):
                suffixSum = 0
                for j in range(i, k - 1, -1):
                    suffixSum += A[j - 1]
                    dp[k][i] = max(dp[k][i], dp[k - 1][j - 1] + suffixSum / (i - j + 1))
        print(dp)
        return max([dp[i][size] for i in range(1, K + 1)])

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        l_A = len(A)

        memo = { (l_A, 0) : 0 }

        def dfs(idx, rem):

            if rem == 0 or l_A - idx < rem:
                return 0

            if rem == 1:
                return sum(A[idx:]) / (l_A - idx)

            if (idx, rem) in memo:
                return memo[(idx, rem)]

            sum_so_far = 0
            avg = 0
            best = 0

            for i in range(idx, l_A):
                sum_so_far += A[i]
                avg = sum_so_far / (i - idx + 1)
                best = max(best, avg + dfs(i + 1, rem - 1))

            memo[ (idx, rem) ] = best
            return best

        return dfs(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if not A or len(A) < K:
            return 0
        for i in range(1, len(A)):
            A[i] += A[i-1]
            
        cache = {}
        
        def cal(n, k):
            if n <= 0 or k <= 0:
                return 0
            if n < k:
                return 0
            if (n, k) in cache:
                return cache[(n, k)]
            if k == 1:
                cache[(n, 1)] = A[n-1] / n
                return cache[(n, 1)]
            res, cur = 0, 0
            for i in range(n-1, 0, -1):
                res = max(res, (A[n-1] - A[i-1]) / (n-i) + cal(i, k-1))
            cache[(n, k)] = res
            return res
        
        return cal(len(A), K)

from functools import lru_cache 
class Solution(object):
    def largestSumOfAverages(self, A, K):
        l = len(A)
        @lru_cache(None)
        def dp(n, k):
            if n < k: return 0
            if k == 1: return sum(A[:n])/float(n)
            cursum, ans = 0, 0
            for i in range(n-1, -1, -1):
                cursum += A[i]
                ans = max(ans, dp(i, k-1) + cursum/float(n-i))
            return ans
        return dp(l, K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[0] * (n + 1) for _ in range(K + 1)]
        sums = [0] * (n + 1)
        for i in range(1, n + 1):
            sums[i] = sums[i - 1] + A[i - 1]
            dp[1][i] = sums[i] / i
        for k in range(2, K + 1):
            for i in range(k, n + 1):
                for j in range(k - 1, i):
                    dp[k][i] = max(dp[k][i], dp[k - 1][j] + (sums[i] - sums[j]) / (i - j))
        return dp[K][n]


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        memo = {}
        
        def dfs(n, K):
            
            if (n, K) in memo:
                return memo[n, K]
            
            if n < K: return 0
            
            if K == 1:
                memo[n, K] = sum(A[:n]) / n
                return memo[n, K]
            
            cur, memo[n, K] = 0, 0
            for i in range(n-1, 0, -1):
                cur += A[i]
                memo[n, K] = max(memo[n, K], dfs(i, K -1 ) + cur / (n - i))
                
            return memo[n, K]
        
        return dfs(len(A), K)

from functools import lru_cache 
class Solution(object):
    def largestSumOfAverages(self, A, K):
        l = len(A)
        revsum = [0] * (l-1) + [A[-1]]
        for i in range(l-1)[::-1]:
            revsum[i] =  revsum[i+1] + A[i]
        # print(revsum)
        @lru_cache(None)
        def dp(n, k):
            if n < k: return 0
            if k==1: return sum(A[:n])/float(n)
            cur, ans = 0, 0           
            for i in range(n-1, 0, -1):
                cur += A[i]
                ans = max(ans, dp(i, k-1) + (revsum[i] - (revsum[n] if n != l else 0))/float(n-i))
            return ans
        return dp(l, K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        if K >= n:
            return sum(A)
        
        pre_sum = [0]
        for num in A:
            pre_sum.append(pre_sum[-1] + num)
        # print(pre_sum)
        if K <= 1:
            return pre_sum[-1] / n
        
        
        dp = [[0] * (K + 1) for _ in range(n)]
        dp[0][1] = A[0]
        for i in range(1, n):
            dp[i][1] = pre_sum[i + 1] / (1 + i)
        
        for k in range(2, K + 1):
            for i in range(k - 1, n):
                for j in range(k - 2, i):
                    
                    dp[i][k] = max(dp[i][k], dp[j][k - 1] + (pre_sum[i + 1] - pre_sum[j + 1]) / (i - j))
                    # print(k, i, j, dp[i][k])
        print(dp)
        return dp[n - 1][K]

import itertools

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # Dynamic Programming 
        # Time  complexity: O(K x N^2)
        # Space complexity: O(N)
        # P = [0] + list(itertools.accumulate(A))
        # def average(i, j): return (P[j] - P[i]) / float(j - i)

        # N = len(A)
        # dp = [average(i, N) for i in range(N)]
        # for _ in range(K - 1):
        #     for i in range(N):
        #         for j in range(i + 1, N):
        #             dp[i] = max(dp[i], average(i, j) + dp[j])

        # return dp[0]


        dp = [[0] * len(A) for _ in range(K)]
        cur_sum = 0

        for j in range(len(A)):
            cur_sum += A[j]
            dp[0][j] = float(cur_sum) / (j + 1)

        for i in range(1, K):
            for j in range(len(A)):
                cur_sum = 0
                for k in range(j, i - 1, -1):
                    cur_sum += A[k]
                    dp[i][j] = max(dp[i][j], dp[i - 1][k - 1] + float(cur_sum) / (j - k + 1))

        return dp[-1][-1]





class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefix = [0]
        for a in A:
            prefix.append(prefix[-1] + a)
        @lru_cache(None)
        def soa(i, k):
            if len(prefix) - 1 - i <= k:
                return prefix[-1] - prefix[i]
            elif k == 1:
                return (prefix[-1] - prefix[i]) / (len(prefix) - 1 - i)
            best = 0
            for j in range(i + 1, len(prefix) - (k - 1)):
                best = max(best, (prefix[j] - prefix[i]) / (j - i) + soa(j, k - 1))
            return best
        return soa(0, K)

class Solution:
     def largestSumOfAverages(self, A, K):
        dp = {}
        def search(n, k):
            if (n, k) in dp: return dp[n, k]
            if n < k: return 0
            if k == 1:
                dp[n, k] = sum(A[:n]) / float(n)
                return dp[n, k]
            cur, dp[n, k] = 0, 0
            for i in range(n - 1, 0, -1):
                cur += A[i]
                dp[n, k] = max(dp[n, k], search(i, k - 1) + cur / float(n - i))
            return dp[n, k]
        return search(len(A), K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        presum = [0] + list(itertools.accumulate(A))
        def mean(i, j):
            return (presum[j+1] - presum[i])/(j-i+1)
        n = len(A)
        old = [[mean(i, j) if i <= j else 0 for j in range(n)] for i in range(n)]
        new = [[0 for j in range(n)] for i in range(n)]
        
        mval = mean(0, n-1)
        
        for k in range(2, K+1):
            # print(f'k={k}')
            for i in range(n-k+1):
                max_val = -float('inf')
                for mid in range(i, n-k+1):
                    max_val = max(max_val, mean(i,mid) + old[mid+1][n-1])
                new[i][n-1] = max_val
            old, new = new, old
            # for x in old:
            #     print(x)
            mval = max(mval, old[0][-1])
        return mval

class Solution:
     def largestSumOfAverages(self, A, K):
        memo = {}
        def search(n, k):
            if (n, k) in memo: return memo[n, k]
            if n < k: return 0
            if k == 1:
                memo[n, k] = sum(A[:n]) / float(n)
                return memo[n, k]
            cur, memo[n, k] = 0, 0
            for i in range(n - 1, 0, -1):
                cur += A[i]
                memo[n, k] = max(memo[n, k], search(i, k - 1) + cur / float(n - i))
            return memo[n, k]
        return search(len(A), K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefix = [A[0]]
        for i in range(1, len(A)):
            prefix.append(prefix[i-1] + A[i])
            
        dp = [[prefix[i]/(i+1) if k == 1 else 0 for k in range(K+1)] for i in range(len(A))]
        
        for i in range(1, len(A)):
            for k in range(2, min(i+2, K+1)):
                val = float('-inf')
                _sum = 0
                for j in range(i, 0, -1):
                    _sum += A[j]
                    val = max(dp[j-1][k-1] + (_sum/(i-j+1)), val)
                dp[i][k] = val
                
        return dp[len(A)-1][K]

from functools import lru_cache
class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        
        l = len(A)
        @lru_cache(None)
        def dp(n, k):
            if n < k: return 0
            if k == 1: return sum(A[:n])/float(n)
            cur, ans = 0, 0
            for i in range(n-1, 0, -1):
                cur += A[i]
                ans = max(ans, dp(i, k-1) + cur/float(n - i))
            return ans
        return dp(l, K)


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        cumsum = [A[0]]
        for i in range(1, len(A)):
            cumsum.append(cumsum[-1] + A[i])
        cumsum.append(0)

        @lru_cache(None)
        def rec(i, K):
            if K == 1:
                return (cumsum[len(A)-1] - cumsum[i-1]) / (len(A)-i)
            return max((cumsum[j] - cumsum[i-1]) / (j-i+1) + rec(j+1, K-1) for j in range(i, len(A)-K+1))

        return rec(0, K)



class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
            
        dp = [[0 for k in range(K+1)] for i in range(len(A))]
        dp[0][1] = A[0]
        
        for count,i in enumerate(range(1,len(A))):
            dp[i][1] = ((dp[i-1][1] * (count + 1)) + A[i]) / (count + 2)
        
        for i in range(1, len(A)):
            for k in range(2, min(i+2, K+1)):
                val = float('-inf')
                _sum = 0
                for j in range(i, 0, -1):
                    _sum += A[j]
                    val = max(dp[j-1][k-1] + (_sum/(i-j+1)), val)
                dp[i][k] = val
                
        return dp[len(A)-1][K]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefix = [A[0]]
        for i in range(1, len(A)):
            prefix.append(prefix[i-1] + A[i])
            
        dp = [[prefix[i]/(i+1) if k == 1 else 0 for k in range(K+1)] for i in range(len(A))]
        
        for i in range(1, len(A)):
            for k in range(2, min(i+2, K+1)):
                val = float('-inf')
                for j in range(1, i+1):
                    val = max(dp[j-1][k-1] + ((prefix[i] - prefix[j-1])/(i-j+1)), val)
                dp[i][k] = val
                
        return dp[len(A)-1][K]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        dp = [[0 for y in range(len(A))] for x in range(K)]
        add=0
        pref=[0 for i in range(len(A))]
        
        for x in range(len(A)):
            add+=A[x]
            pref[x]=add
        # print(pref)
        for x in range(len(A)):
            dp[0][x] = (pref[x]/(x+1))
        for y in range(1,K):
            dp[y][0] = A[0]
        for x in range(1,K):
            for y in range(1,len(A)):
                val1 = (pref[y]/(y+1))
                maxi = val1
                # print(\"hi\")
                for z in range(y):
                    val = dp[x-1][z] + ((pref[y]-pref[z])/(y-z))
                    # print(x,y,z,val)
                    maxi=max(maxi,val)
                dp[x][y]=maxi
        # print(dp)
        return (dp[-1][-1])
                


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:    
        dp = [[A[0] if k == 1 else 0 for k in range(K+1)]]
        
        for count, i in enumerate(range(1,len(A))):
            dp.append([0])
            dp[i].append(
                ((dp[i-1][1] * (count + 1)) + A[i]) / (count + 2)
            )
        
        for i in range(1, len(A)):
            for k in range(2, K+1):
                val = float('-inf')
                _sum = 0
                for j in range(i, 0, -1):
                    _sum += A[j]
                    val = max(dp[j-1][k-1] + (_sum/(i-j+1)), val)
                dp[i].append(val)
        
        return dp[len(A)-1][K]

class Solution:
    def largestSumOfAverages(self, A, K):
        m = len(A)
        dp = [[None] * (K + 1) for _ in range(m)]
        for k in range(1, K + 1):
            for j in range(k - 1, m):
                if k == 1:
                    dp[j][k] = sum(A[:j + 1]) / (j + 1)
                else:
                    dp[j][k] = max(dp[i][k - 1] + sum(A[i + 1:j + 1]) / (j - i) for i in range(k - 2, j))
        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n=len(A)
        sum_zero2i=[0]*(n+1)
        for i in range(1, n+1):
            sum_zero2i[i]=sum_zero2i[i-1]+A[i-1]
        
        dp=[0]*n
        for i in range(n):
            dp[i]=(sum_zero2i[-1] - sum_zero2i[i])/ (n-i)
        
        for _ in range(K-1):
            for i in range(n):
                for j in range(i+1,n):
                    dp[i]=max(dp[i], dp[j]+ ( (sum_zero2i[j]-sum_zero2i[i])/ (j-i)  ))    
        return dp[0]
        
        
        
        
        
        
        O(k*N^2)    


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        suffix_sums = [0] * (len(A) + 1)
        for i in range(len(A) - 1, -1, -1):
            suffix_sums[i] = A[i] + suffix_sums[i + 1]
            
        memo = {}
        def largest_starting_at(i, new_k):
            if i == len(A):
                return 0
            if new_k == 1:
                return suffix_sums[i] / (len(A) - i)
            if (i, new_k) in memo:
                return memo[i, new_k]
            best = 0
            for size in range(1, len(A) - i):
                best = max(
                    best,
                    (suffix_sums[i] - suffix_sums[i + size]) / size + largest_starting_at(i + size, new_k - 1)
                )
            memo[i, new_k] = best
            return memo[i, new_k]
        
        return largest_starting_at(0, K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefix = [A[0]]
        for i in range(1, len(A)):
            prefix.append(prefix[i-1] + A[i])
            
        dp = [[prefix[i]/(i+1) if k == 1 else 0 for k in range(K+1)] for i in range(len(A))]
        
        for i in range(1, len(A)):
            for k in range(2, K+1):
                val = float('-inf')
                for j in range(1, i+1):
                    val = max(dp[j-1][k-1] + ((prefix[i] - prefix[j-1])/(i-j+1)), val)
                dp[i][k] = val
                
        return dp[len(A)-1][K]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n=len(A)
        sum_i2end=[0]*(n+1)
        for i in range(1, n+1):
            sum_i2end[i]=sum_i2end[i-1]+A[i-1]
        
        dp=[0]*n
        for i in range(n):
            dp[i]=(sum_i2end[-1] - sum_i2end[i])/ (n-i)
        
        for _ in range(K-1):
            for i in range(n):
                for j in range(i+1,n):
                    dp[i]=max(dp[i], dp[j]+ ( (sum_i2end[j]-sum_i2end[i])/ (j-i)  ))    
        return dp[0]

            




class Solution:

    def largestSumOfAverages(self, A, K: int) -> float:
        def avg(array):
            return sum(array) / len(array)
        # dp [i->sub list of A til ith ele][p->how many parts]
        dp = [[0 for _ in range(K + 1)] for _ in range(len(A))]
        means = [[0 for _ in range(len(A))] for _ in range(len(A))]

        for i in range(len(A)):
            for j in range(i, len(A)):
                # include i include j
                # means[i][j] = statistics.mean(A[i:j + 1])
                means[i][j] = avg(A[i:j + 1])

        for i in range(len(A)):
            dp[i][1] = means[0][i]

        for i in range(1, len(A)):
            for j in range(2, min(K + 1, i + 1 + 1)):
                # k+1 last_stop_index+1 -> if stop at index 2 we can divide up to 2+1 = 3 groups,  j-1 prev_groups
                for k in range(max(i - 1, j - 1 - 1), -1, -1):
                    # k exclude, i included
                    temp_last_group = means[k + 1][i]
                    temp_sum_prev = dp[k][j - 1]
                    dp[i][j] = max(
                        dp[i][j], temp_last_group + temp_sum_prev)

        return dp[-1][-1]

    # def largestSumOfAverages(self, A, K: int) -> float:

    #     if K == 0:
    #         return mean(A)

    #     lis_len = len(A)
    #     if K >= lis_len:
    #         return sum(A)
    #     means = [[0 for _ in range(lis_len)] for _ in range(lis_len)]
    #     # print(means)

    #     for i in range(lis_len):
    #         for j in range(i, lis_len):
    #             # print(i,j,mean(A[i:j+1]))
    #             means[i][j] = mean(A[i:j+1])

    #     dp = [[0 for _ in range(lis_len + 1)] for _ in range(K + 1)]

    #     for i in range(1, lis_len + 1):
    #         # dp[1][i] = mean(A[:i])
    #         dp[1][i] = means[0][i-1]

    #     for i in range(2, K + 1):
    #         for j in range(i, lis_len + 1):
    #             # temp_lis = []
    #             local_max = 0
    #             for p in range(1, j):
    #                 # temp = dp[i - 1][p] + mean(A[p:j])
    #                 temp = dp[i-1][p]+means[p][j-1]
    #                 # print(A[p:j],mean(A[p:j]),means[p][j-1],p,j-1)

    #                 import sys
    #                 # return
    #                 # temp = dp[i - 1][p] + means[p-1][j]

    #                 if temp > dp[i][j]:
    #                     dp[i][j] = temp
    #                 # temp_lis.append(temp)
    #             # dp[i][j] = max(temp_lis)

    #     return dp[K][lis_len]


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        n = len(A)
        dp = [[-math.inf] * K for _ in range(n)]
        sv, sc = 0, {-1:0}
        for i, v in enumerate(A):
            sv += v
            sc[i] = sv
        dp[0][0] = A[0]
        for r in range(n):
            for i in range(0, r):
                for k in range(min(K, r+1)):
                    if k == 0:
                        dp[r][k] = (sc[r]-sc[-1])/(r+1)
                    else:
                        candidate = dp[i][k-1] + (sc[r]-sc[i])/(r-i) 
                        dp[r][k] = max(dp[r][k], candidate)
        # for row in dp:
        #     print(row)
        return dp[-1][-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        def helper(n,k):
            if (n,k) in dp: return dp[n,k]
            if k==1: return sum(A[:n])/n
            if n<=k: return sum(A[:n])
            dp[n,k],temp = 0,0
            for i in range(1,n)[::-1]:
                temp+=A[i]
                dp[n,k]=max(dp[n,k],helper(i,k-1)+temp/(n-i))
            return dp[n,k]
            
        dp = {}
        return helper(len(A),K)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefixSum = [0]
        for x in A:
            prefixSum.append(prefixSum[-1] + x)
            
        def avg(i, j):
            return (prefixSum[j] - prefixSum[i]) / (j - i)
        
        n = len(A)
        dp = [avg(i, n) for i in range(n)]
        for k in range(K-1):
            for i in range(n):
                for j in range(i+1, n):
                    dp[i] = max(dp[i], avg(i, j) + dp[j])
                    
        return dp[0]

class Solution(object):
    def largestSumOfAverages(self, A, K):
        p=[0]
        for x in A:
            p.append(x+p[-1])
        def avg(i,j):
            return (p[j]-p[i])/(j-i)
        N=len(A)
        dp=[avg(i,N) for i in range(N)]
        for k in range(K-1):
            for i in range(N):
                for j in range(i+1,N):
                    dp[i]=max(dp[i],avg(i,j)+dp[j])
        return dp[0]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        @lru_cache(None)
        def helper(i,t):
            if(i>=len(A)):
                return 0
            if(t==K-1):
                return sum(A[i:])/(len(A)-i)
            else:
                m=-1
                for j in range(1,len(A)-i):
                    m=max(m,helper(i+j,t+1)+sum(A[i:i+j])/j) 
                return m
        return helper(0,0)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        N = len(A)

        @lru_cache(None)
        def dfs(index, remain):
            if remain <= 0:
                return sum(A[index:]) / (N - index)
            if index >= N:
                return 0
            ans = 0
            for i in range(index + 1, N):
                ans = max(ans, sum(A[index:i]) / (i - index) + dfs(i, remain - 1))
            return ans

        res = dfs(0, K - 1)
        return res

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if K == 1:
            return sum(A)/len(A)
        biggest = [[[None for temp in range(K+1)] for col in range(len(A))] for row in range(len(A))]
        for start in range(len(A)):
            for end in range(start,len(A),1):
                biggest[start][end][1] = sum(A[start:end+1])/len(A[start:end+1])
        for curK in range(2,K+1):
            startEnd = len(A)-curK+1
            if curK == K:
                startEnd = 1
            for start in range(0,startEnd,1):
                tempNo = 0
                for middle in range(start,len(A)-curK+1,1):
                    theNo = biggest[start][middle][1] + biggest[middle+1][len(A)-1][curK-1]
                    if theNo > tempNo:
                        tempNo = theNo
                biggest[start][len(A)-1][curK] = tempNo

            
        return (biggest[0][len(A)-1][K])


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        @lru_cache(None)
        def helper(i,t):
            if(i>=len(A)):
                return 0
            if(t==K-1):
                return sum(A[i:])/(len(A)-i)
            else:
                m=-1
                for j in range(1,len(A)-i):
                    m=max(m,helper(i+j,t+1)+sum(A[i:i+j])/j) 
                    if(t==3):
                        print(m)
                return m
        return helper(0,0)

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if len(A) <= K:
            return sum(A)
        A1 = []
        s = 0
        for i in A:
            s += i
            A1.append(s)
        n = len(A)
        last = [A1[i] / (i+1) for i in range(n)]
        for k in range(1, K):
            cur = [A[0]]
            for i in range(1, n):
                stage_max = 0
                for j1, j in enumerate(last[:i]):
                    stage_max = max(stage_max, j + (A1[i]-A1[j1]) / (i - j1))
                cur.append(stage_max)
            last = cur
        return last[-1]
                
            
            


class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        L = len(A)
        
        # reduced_dp[i] store the value of dp[i][K]
        # the `k` in dp[i] is implicity indicated by the loop
        reduced_dp = [0 for _ in range(L)]        
        prefix_sum = [0 for _ in range(L + 1)]
        for i in range(1, L + 1):
            prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
            reduced_dp[i - 1] = prefix_sum[i] / i;

        # for i in reduced_dp:
        #     print(i)

        for k in range(2, K + 1):
            for i in reversed(range(1, L)):
                if k <= i + 1:
                    for j in range(-1, i):
                        ave = (prefix_sum[i + 1] - prefix_sum[j + 1]) / (i - j)
                        if j == -1:
                            tmp = 0
                        else:
                            tmp = reduced_dp[j]
                        if ave + tmp > reduced_dp[i]:
                            reduced_dp[i] = ave + tmp
                            
        # for i in reduced_dp:
        #     print(i)
        # print('done')
        return reduced_dp[-1]

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        prefix = [0] + A.copy()
        for i in range(1, len(prefix)):
            prefix[i] += prefix[i - 1]
         
        def query(i, j): # inclusive
            return prefix[j + 1] - prefix[i]
        
        def get_average(i, j):
            return query(i, j) / (j - i + 1)
        
        N = len(A)
        cache = {}
        def dfs(i, k):
            if k < 0:
                return -float('inf')
            
            if (i, k) in cache:
                return cache[(i, k)]
            
            if i == N:
                if k == 0:
                    return 0
                else:
                    return -float('inf')
                
            res = -float('inf')
            for j in range(i, N):
                take = dfs(j + 1, k - 1) + get_average(i, j)
                res = max(res, take)
                
            cache[(i, k)] = res
            return res
        
        
        return dfs(0, K)

class Solution: #1037
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        if not A:
            return 0
        dp = {}
        averages = [[None] * len(A) for _ in range(len(A))]
        for i in range(len(A)):
            averages[i][i] = A[i]
            for j in range(i+1, len(A)):
                averages[i][j] = (averages[i][j-1] * (j-i) + A[j]) / (j-i+1)
        def recurse(A, K, start):
            if start >= len(A):
                return 0
            if K == 1:
                return averages[start][len(A)-1]
            if (K, start) in dp:
                return dp[K, start]
            dp[K, start] = -math.inf
            for i in range(start, len(A)):
                dp[K, start] = max(dp[K, start], averages[start][i] + recurse(A, K-1, i+1))
            return dp[K, start]
        return recurse(A, K, 0)

from itertools import combinations
from functools import lru_cache
class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        #brute force...how many ways are there to partition an array?
        # cubic time for n>>3
        # the questoin says: AT MOST K, so we could get away with K = 1
        # but K =1 is always the smallest (largest divisor in the mean)
        # I wonder if greedy would work
        def mean(A):
            return sum(A)/len(A);
        @lru_cache(None)
        def recurse(start, end, k = 1):
            if(k == K):
                return mean(A[start:end]);
            if(len(A) == 1):
                return A[0]
            maxval = 0;
            for i in range(start+1,end):
                maxval = max(maxval, mean(A[start:i])+recurse(i, end, k+1));
            return maxval
            
        # def recurse(A, k = 1):
        #     if(k == K):
        #         return mean(A);
        #     if(len(A) == 1):
        #         return A[0]
        #     N = len(A);
        #     maxval = 0;
        #     # print(A)
        #     for i in range(1,N):
        #         split1 = A[0:i]
        #         split2 = A[i:N]
        #         maxval = max(maxval, mean(split1)+recurse(split2,k+1))
        #     return maxval
                
        N = len(A)
        return recurse(0,N)

class Solution(object):
    def largestSumOfAverages(self, A, K):
        prefix_sum = [0]
        for x in A:
            prefix_sum.append(prefix_sum[-1] + x)
        
        def average(i, j):
            return (prefix_sum[j] - prefix_sum[i]) / float(j - i)

        n = len(A)
        dp = [average(i, n) for i in range(n)]
        print(dp)
        
        for k in range(K-1):
            for i in range(n):
                for j in range(i+1, n):
                    dp[i] = max(dp[i], average(i, j) + dp[j])
        return dp[0]        

class Solution:
    def largestSumOfAverages(self, A: List[int], K: int) -> float:
        # dp[i][k]: max avg sum to divide A[:i] into k sub group
        n = len(A)
        dp = [[0 for _ in range(K + 1)] for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for k in range(1, K + 1):
                if k == 1:
                    dp[i][k] = sum(A[:i]) / i
                else:
                    for j in range(k, i + 1):
                        dp[i][k] = max(dp[i][k], dp[j - 1][k - 1] + sum(A[j - 1: i]) / (i - j + 1))
        
        return dp[n][K]