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.


  • 2
    V

    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;
        }
    }
    

  • 0
    R

    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.


  • 0
    V

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


  • 1
    V

    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.


  • 0
    Y

    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.


Log in to reply
 

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