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 [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20. We could have also partitioned nums into [9, 1], [2], [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 = [0]
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[0]
}
Copy The Code &
Try With Live Editor
Input
Output
#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 &
Try With Live Editor
Input
Output