Участник: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):