package leetcode;

/**
 * https://leetcode.com/problems/largest-sum-of-averages/
 */
public class Problem813 {
    public double largestSumOfAverages(int[] A, int K) {
        Double[][] memo = new Double[K + 1][A.length];
        return largestSumOfAverages(A, K, 0, memo);
    }

    private static double largestSumOfAverages(int[] a, int k, int idx, Double[][] memo) {
        if (idx == a.length || k == 0) {
            return 0;
        }
        if (memo[k][idx] != null) {
            return memo[k][idx];
        }
        int size = 1;
        double sum = 0;
        double max = 0;
        for (int i = idx; i < a.length; i++) {
            sum += a[i];
            double avg = (sum / size);
            max = Math.max(max, largestSumOfAverages(a, k - 1, i + 1, memo) + avg);
            size++;
        }
        memo[k][idx] = max;
        return max;
    }

    public static void main(String[] args) {
        Problem813 prob = new Problem813();
        System.out.println(prob.largestSumOfAverages(new int[]{9, 1, 2, 3, 9}, 3)); // 20
        System.out.println(prob.largestSumOfAverages(new int[]{1, 2, 3, 4, 5, 6, 7}, 4)); // 20.5
        System.out.println(prob.largestSumOfAverages(new int[]{4, 1, 7, 5, 6, 2, 3}, 4)); // 18.16667
    }
}

@@ -397,18 +397,8 @@
 ngth
- %7C%7C k == 0
 ) %7B%0A
@@ -421,32 +421,87 @@
 rn 0;%0A        %7D%0A
+        if (k == 0) %7B%0A            return -1;%0A        %7D%0A
         if (memo
@@ -730,17 +730,16 @@
 e avg = 
-(
 sum / si
@@ -740,17 +740,16 @@
 m / size
-)
 ;%0A      
@@ -758,27 +758,19 @@
     
-max = Math.max(max,
+double sa =
  lar
@@ -813,15 +813,8 @@
 emo)
- + avg)
 ;%0A  
@@ -827,15 +827,23 @@
     
-size++;
+if (sa != -1) %7B
 %0A   
@@ -839,34 +839,32 @@
 = -1) %7B%0A        
-%7D%0A
         memo%5Bk%5D%5B
@@ -860,432 +860,129 @@
    m
-emo%5Bk%5D%5Bidx%5D = max;%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem813 prob = new Problem813();%0A        System.out.println(prob.largestSumOfAverages(new int%5B%5D%7B9, 1, 2, 3, 9%7D, 3)); // 20%0A        System.out.println(prob.largestSumOfAverages(new int%5B%5D%7B1, 2, 3, 4, 5, 6, 7%7D, 4)); // 20.5%0A        System.out.println(prob.largestSumOfAverages(new int%5B%5D%7B4, 1, 7, 5, 6, 2, 3%7D, 4)); // 18.16667
+ax = Math.max(max, sa + avg);%0A            %7D%0A            size++;%0A        %7D%0A        memo%5Bk%5D%5Bidx%5D = max;%0A        return max;
 %0A   

Solve problem 813