813. Largest Sum of Averages

It is a classical O(n^3) DP problem
Related Problems
LC 139 Word Break
LC 312 Burst Balloons
It also looks like the buying stock series of problems

二刷 06/2022

Version #2 DP with optimized space

这里的dp可以有两个定义

第一种就是a划分成exactly K partitions, 第二种是bat most K partitions

Time O(KN^2)

Space O(N)

Version 2.a

Exactly K partitions，需要对每个K的dp[len]都取一次max

class Solution {

    public double largestSumOfAverages(int[] nums, int k) {

        int len = nums.length;

        int[] prefixSum = new int[len + 1];

        // prefixSum[i] - the sum of nums [0, i)

        for (int i = 1; i <= len; i++) {

            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];

        }

        // dp[i] - the max score to partition nums [0, i) into n groups

        double max = 0.0;

        double[] dp = new double[len + 1];

        for (int n = 1; n <= k; n++) {

            double[] currDP = new double[len + 1];

            for (int i = 1; i <= len; i++) {

                if (n == 1) {

                    // to split sub array [0, i) into 1 partition

                    currDP[i] = (double)(prefixSum[i] - prefixSum[0]) / i;

                } else {

                   for (int j = i - 1; j >= n - 1; j--) {

                        currDP[i] = Math.max(currDP[i], dp[j] + (double)(prefixSum[i] - prefixSum[j]) / (i - j));

                    }     

                } 

                

                if (i == len) {

                    max = Math.max(max, currDP[i]);

                }

            }

            dp = currDP;

        }

        return max;

    }

}

Version 2.b

class Solution {

    public double largestSumOfAverages(int[] nums, int k) {

        int len = nums.length;

        int[] prefixSum = new int[len + 1];

        // prefixSum[i] - the sum of nums [0, i)

        for (int i = 1; i <= len; i++) {

            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];

        }

        // dp[i] - the max score to partition nums [0, i) into n groups

        double max = 0.0;

        double[] dp = new double[len + 1];

        for (int n = 1; n <= k; n++) {

            double[] currDP = new double[len + 1];

            for (int i = 1; i <= len; i++) {

                if (n == 1) {

                    // to split sub array [0, i) into 1 partition

                    currDP[i] = (double)(prefixSum[i] - prefixSum[0]) / i;

                } else {

                   for (int j = i - 1; j >= 0; j--) {

                        currDP[i] = Math.max(currDP[i], dp[j] + (double)(prefixSum[i] - prefixSum[j]) / (i - j));

                    }     

                } 

                // if (i == len) {

                //     max = Math.max(max, currDP[i]);

                // }

            }

            dp = currDP;

        }

        return dp[len];

    }

}

一刷
Version # 1 DP (Space can be optimized)
Time O(n^2 k)
Space O(nk)

44.02 %
class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        // dp[i][m] - partition previous[0,i] items into m groups where m >= 1, m <= i + 1, m <= K
        // dp[i][m] = Math.min(dp[j][m-1]) + avg(A[j+1, i])
        int len = A.length;
        double sum = 0;
        double[][] dp = new double[len][K + 1];
        for (int i = 0; i < len; i++) {
            sum += A[i]; // sum[0, A[i]]
            // K = 0 -> don't partition
            dp[i][1] = sum / (i + 1); // the average of A[0, i], m = 0 is invalid
            for (int m = 2; m <= Math.min(i + 1, K); m++) { // partition previous i numbers into m groups m -> [1, Math.min(i + 1, K)]
                double subSum = 0;
                double avg = 0;
                for (int j = i - 1; j >= 0; j--) {
                    // [0,j][j+1,i]
                    subSum += A[j + 1];
                    avg = Math.max(avg, dp[j][m - 1] + subSum / (i - j));
                }
                dp[i][m] = avg;
            }
        }
        return dp[len - 1][K];
    }
}