# Dear friends, please take a look at this code, It passes 70 test cases. gives me incorrect response on the 71st one. I am not sure what is going wrong.

• Idea is : avg[i] = max( (avg[i - 1] * len[i - 1] + nums[i]) / (len[i - 1] + 1), sum /k);

Where sum is the running sum which keeps sum of last k elements. avg[i] represents max average of the array which ends at ith index. len[i] keeps track of how many numbers used to compute the max average that ends at ith index.

``````public class Solution {
public double findMaxAverage(int[] nums, int k) {
double sum = 0, maxAvg = Integer.MIN_VALUE;
double[] sums = new double[nums.length];
int[] lens = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) {
sum -= nums[i - k];
double prev = (sums[i - 1] + nums[i]) / (lens[i - 1] + 1);
double curr = sum / k;
if (prev > curr) {
sums[i] = sums[i - 1] + nums[i];
lens[i] = lens[i - 1] + 1;
} else {
sums[i] = sum;
lens[i] = k;
}
maxAvg = Math.max(maxAvg, sums[i]/lens[i]);
}
if (i + 1 == k) {
sums[i] = sum;
lens[i] = k;
maxAvg = sum/k;
}
}

return maxAvg;
}
}
``````

• I got the same idea of DP.
And get the same failure at 71st test case.

I used the brute force algorithm verified the test case.
It return [15, 99] with average 47.05882.

But, this DP will return [6, 99] with average 47.05319.

[65,91,27,13,3,39,78,76,0,60,27,63,36,36,47,75,38,93,35,53,71,51,5,17,72,57,90,14,20,62,53,37,6,80,2,9,71,80,38,24,40,65,39,77,53,87,4,44,32,40,49,4,43,6,73,15,63,15,81,35,78,34,24,84,67,26,45,90,6,83,66,99,1,6,76,6,45,32,50,29,72,99,33,15,5,6,82,21,74,15,56,52,50,81,88,69,7,85,59,66]
70

It's not a problem of loss accuracy.

Seems like this DP transform is not correct. But, I can't figure out where the logic failed neither.

• Hmm.. may be we should come up with some formal proof of correctness :)

• I am convinced that our optimal substructure is incorrect, to prove the claim I came up with a simple counter example.

let us say in the (i - 1)th step, we have 2 averages which cover 1 and 2 elements respectively the elements are 5 and 5, 4 respectively. Their corresponding averages are 5 and 4.5. our approach puts avg[i - 1] = 5.

Now let us say, next element in the sequence is 1. The DP chooses (5 + 1)/ 2 = 3 for avg[i]. But we can we get better average with (5 + 4 + 1) / 3 = 3.33.

Therefore our DP optimal substructure is incorrect.

• Use an example to explain.
DP idea: dp[i] is the largest average value end with nums[i]
if we have an array [46, 46, 46, 47, 47, 47, 1] k = 3;
so dp array is [0, 0, 46, (47+46+46)/3, (47+47+46)/3 ,47 ,(47+47+47+1)/4)]
but the correct answer for last element in dp array should be (46+46+46+47+47+47+1)/7.

• [46, 46, 46, 47, 47, 47, 1]

you are wrong.

The formula is like this:
if x/y > i/j, can you conclude that x+m/y+1 > i+m/j+1?
x, i denote the total sum while y, j represent the length.
I came up with the same idea but did not get accepted.

• I added a for-loop check at the end based on the idea above. And all test cases passed. Beat 100%.

I'm not sure about the correctness though ;)

``````class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
prevSum = 0
prevCount = 0
s = 0
e = 0
kSum = 0
mx = float('-inf')
sol = None
while e < len(nums):
kSum += nums[e]
if e - s + 1 > k:
prevSum += nums[s]
prevCount += 1
kSum -= nums[s]
s += 1
if (prevSum * 1.0 / prevCount) <= (kSum * 1.0 / k):
prevSum, prevCount = 0, 0
if e - s + 1 == k:
avg = (kSum + prevSum) * 1.0 / (k + prevCount)
if mx < avg:
mx = avg
sol = (prevCount, s, e, kSum)
e += 1
prevCount, s, e, sm = sol
for i in range(0, prevCount):
pos = s - i - 1
sm += nums[pos]
mx = max(mx, sm * 1.0 / (k + i + 1))
return mx
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.