package leetcode;

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

    private static double largestSumOfAverages(int[] a, int k, int idx) {
        if (idx == a.length || k == 0) {
            return 0;
        }
        int size = 1;
        double max = 0;
        for (int i = idx; i < a.length; i++) {
            double avg = (a[i] / size);
            max = Math.max(max, largestSumOfAverages(a, k - 1, i + 1) + avg);
            size++;
        }
        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
    }
}

@@ -157,24 +157,79 @@
 A, int K) %7B%0A
+        Double%5B%5D%5B%5D memo = new Double%5BK + 1%5D%5BA.length%5D;%0A
         retu
@@ -259,16 +259,22 @@
 (A, K, 0
+, memo
 );%0A    %7D
@@ -345,16 +345,33 @@
  int idx
+, Double%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -431,32 +431,111 @@
 rn 0;%0A        %7D%0A
+        if (memo%5Bk%5D%5Bidx%5D != null) %7B%0A            return memo%5Bk%5D%5Bidx%5D;%0A        %7D%0A
         int size
@@ -540,16 +540,40 @@
 ze = 1;%0A
+        double sum = 0;%0A
         
@@ -631,24 +631,49 @@
 gth; i++) %7B%0A
+            sum += a%5Bi%5D;%0A
             
@@ -686,20 +686,19 @@
  avg = (
-a%5Bi%5D
+sum
  / size)
@@ -767,16 +767,22 @@
 1, i + 1
+, memo
 ) + avg)
@@ -805,32 +805,60 @@
 ze++;%0A        %7D%0A
+        memo%5Bk%5D%5Bidx%5D = max;%0A
         return m
@@ -1047,18 +1047,16 @@
 ; // 20%0A
-//
         
@@ -1145,16 +1145,118 @@
 // 20.5%0A
+        System.out.println(prob.largestSumOfAverages(new int%5B%5D%7B4, 1, 7, 5, 6, 2, 3%7D, 4)); // 18.16667%0A
     %7D%0A%7D%0A

Update problem 813