## Algorithm

Problem Name: 813. Largest Sum of Averages

You are given an integer array `nums` and an integer `k`. You can partition the array into at most `k` non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in `nums`, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within `10-6` of the actual answer will be accepted.

Example 1:

```Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation:
The best choice is to partition nums into , [1, 2, 3], . The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], , [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
```

Example 2:

```Input: nums = [1,2,3,4,5,6,7], k = 4
Output: 20.50000
```

Constraints:

• `1 <= nums.length <= 100`
• `1 <= nums[i] <= 104`
• `1 <= k <= nums.length`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const largestSumOfAverages = function(A, K) {
const len = A.length
const P = 
for(let i = 0; i < len; i++) {
P[i+1] = (P[i] || 0) + A[i]
}
const dp = []
for(let j = 0; j < len; j++) {
dp[j] = (P[len] - P[j]) / (len - j)
}
for(let m = 0; m < K - 1; m++) {
for(let n = 0; n < len; n++) {
for(let k = n + 1; k < len; k++) {
dp[n] = Math.max(dp[n], (P[k] - P[n]) / (k - n) + dp[k])
}
}
}
return dp
}
``````
Copy The Code &

Input

cmd
nums = [9,1,2,3,9], k = 3

Output

cmd
20.00000

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def largestSumOfAverages(self, A, K):
memo = {}
def search(n, k):
if n < k: return 0
if (n, k) not in memo:
if k == 1: memo[n, k] = sum(A[:n]) / float(n)
else:
cur = memo[n, k] = 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)
``````
Copy The Code &

Input

cmd
nums = [9,1,2,3,9], k = 3

Output

cmd
20.00000