Daily LeetCode – day0122 0813. Largest Sum of Averages

// 0813. Largest Sum of Averages
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int len = nums.length;
        double[] prefixSum = new double[len + 1];
        for (int i = 0; i < len; ++i) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        double[][] largestSums = new double[len + 1][k + 1];
        for (int i = 1; i <= len; ++i) {
            largestSums[i][1] = prefixSum[i] / i;
        }
        for (int j = 2; j <= k; ++j) {
            for (int i = j; i <= len; ++i) {
                for (int mid = j - 1; mid < i; ++mid) {
                    largestSums[i][j] = Math.max(largestSums[i][j], (prefixSum[i] - prefixSum[mid]) / (i - mid) + largestSums[mid][j - 1]);
                }
            }
        }
        return largestSums[len][k];
    }
}

学习笔记：
这虽然是一道中等题，但其实很苦难。
其实每一个数字分开，那是比较简单的，但是很难分得开，因为k是比较小的。
用的了动态规划和前缀和，主要是状态转移方程式特别难写难想。