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: MEDIUM
Tags: Dynamic programming

Data structures

Range queries
Skill types: Dynamic programming

Data structures

Range queries

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:
		N = len(A)
		P = [0] * (N + 1)
		for i in range(1, N + 1):
			P[i] = P[i - 1] + A[i - 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]


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]


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:
		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]

		def dfs(i, k):
			if k == 1:
				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:
		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:

	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]


class Solution:

	def largestSumOfAverages(self, A: List[int], K: int) -> float:
		import itertools
		cumsum = list(itertools.accumulate(A))
		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)
		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
		return dp[-1][K]


class Solution:

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

		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 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]
						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
		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:

		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 = [[0 for i in range(len(A) + 1)] for j in range(K + 1)]
		cum[0] = 0
		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 = dp(0, 1, K)
		print(maxSum)
		return maxSum


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 = {}
		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)
		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)
		mtr = [[0 for i in range(n + 1)] for j in range(k + 1)]

		def rec(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)
		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)]
		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:
		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)
		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 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]


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 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)
		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, 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:
		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: 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:

		@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:

		@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
		current_best = [0] * num_count
		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):
			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)
				memoDict[i, k] = max_sum
				return max_sum
		flips = recurse(0, K - 1)
		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]


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:

	def largestSumOfAverages(self, A: List[int], K: int) -> float:
		if not A:
			return 0
		n = len(A)
		sums = [0] * (n + 1)
		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):
				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)])


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):
			for w in range(1, K + 1):
				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):
					B[m][w] = max(B[m][w], B[m - e][w - 1] + (S[m] - S[m - e]) / e)
		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:
		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
				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


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)
		if K >= n:
			return sum(A)
		pre_sum = [0]
		for num in A:
			pre_sum.append(pre_sum[-1] + num)
		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(dp)
		return dp[n - 1][K]


import itertools

class Solution:

	def largestSumOfAverages(self, A: List[int], K: int) -> float:
		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: 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):
			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)
			mval = max(mval, old[0][-1])
		return mval


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]


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:
		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
		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
				for z in range(y):
					val = dp[x - 1][z] + (pref[y] - pref[z]) / (y - z)
					maxi = max(maxi, val)
				dp[x][y] = maxi
		return dp[-1][-1]


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:
		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, K: int) -> float:

		def avg(array):
			return sum(array) / len(array)
		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)):
				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)):
				for k in range(max(i - 1, j - 1 - 1), -1, -1):
					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]


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)
		return dp[-1][-1]


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:
		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:
		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 = [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 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
		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):
			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:

	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:

		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
		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]