[LeetCode] Maximum Average Subarray I

Problem: You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

Approach: This is clearly a sliding window problem. We can take sum of first k elements say 'sum' and then we slide the window by one i.e. remove first element of window from sum and add new element of the slided window to sum and record the max sum so far so every step looks like:

• sum = sum - nums[start] + nums[i] 
• start++
• max_sum = MAX(sum, max_sum)

Implementation in C#:

        public double FindMaxAverage(int[] nums, int k)

    {

        int length = nums?.Length ?? 0;

        if (length < k)

        {

            return 0;

        }

        long sum = 0;

        int i = 0, start = 0;

        for (; i < k; ++i)

        {

            sum += nums[i];

        }

        long maxSum = sum;

        for (i = k; i < length; ++i)

        {

            sum = sum - nums[start++] + nums[i];

            maxSum = sum > maxSum ? sum : maxSum;

        }

        return (double)maxSum / k;

    }

Complexity: O(n)