Short C# solution with sliding window on rolling sum


  • 0
    G

    Calculate rolling sums. Keep a local maximum when moving left pointer.

        public double FindMaxAverage(int[] nums, int k)
        {
            double[] sums = new double[nums.Length+1];
            sums[0] = 0;
            
            for (int i =0;i<nums.Length;i++)
            {
                sums[i+1] = sums[i] + nums[i];
            }
            
            int left = 0, right = k;
            double res = (sums[right] - sums[left]) / (right-left);
            while (right <nums.Length)
            {
                double localMax = (sums[++right] - sums[left]) / (right-left);
                int newLeft = left;
                while (right - left > k)
                {
                    double temp = (sums[right] - sums[++left]) / (right-left);
                    if (temp > localMax)
                    {
                        localMax = temp;
                        newLeft = left;
                    }                               
                }
                
                left = newLeft;
                res = Math.Max(res, localMax);
            }
            
            return res;
        }
    

  • 0
    C

    @greatpat This works, but it's O(n^2), plus O(n) space.

    I got 572ms execution runtime for your code, surprisingly beats 23.53%


Log in to reply
 

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