LeetCode 813. 最大平均值和的分组 C#
原题链接
中等
作者:
hpstory
,
2022-11-28 21:51:21
,
所有人可见
,
阅读 131
C# 代码
public class Solution {
public double LargestSumOfAverages(int[] nums, int k) {
int n = nums.Length;
double[] sum = new double[n + 1];
for (int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + nums[i - 1];
}
double[,] dp = new double[n + 1, k + 1];
// dp[i, 0]无意义,需要设置成int.MinValue,防止影响后面计算结果
for (int i = 1; i <= n; i++) dp[i, 0] = int.MinValue;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
for (int len = 0; len < i; len++){
double avg = (sum[i] - sum[len]) / (i - len);
dp[i, j] = Math.Max(dp[i, j], dp[len, j - 1] + avg);
}
}
}
return dp[n, k];
}
}