Участник:Rublev.mv/largest-sum-of-averages

Материал из DISCOPAL
Перейти к: навигация, поиск
 
class Solution {
  public double largestSumOfAverages(int[] A, int K) {   
    int[] s = new int[A.length];
    s[0]=A[0];
    for (int i = 1; i < A.length; i++) {          
        s[i] = A[i] + s[i - 1];
    }
    return lsa(A, K, s, A.length, 0);
  }
  public double lsa(int[] A, int K, int[] s, int r, int l) {
    if (K == 1) {
       return ((double) (s[r - 1] - s[l] + A[l]) / (r- l));
    }
    double res=0.0;
    double tmp=0.0;
    for (int ind = l; ind + K <= r; ind++) {
    tmp= ((double) (s[ind] - s[l] + A[l]) / (ind - l + 1));   
    res = Math.max(res,tmp + lsa(A, K-1, s, r,ind+1));
    }
    return res;
 
    }
}

StasFomin 19:17, 16 декабря 2020 (MSK):

Largest-sum-of-averages 2020-12-16 19-17-28 image0.png