Maximum Average Subarray I - Sliding Window

Problem is here: https://leetcode.com/problems/maximum-average-subarray-i/

643. Maximum Average Subarray I
Easy
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:
  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

Because it gives the length k, you can perform a direct sliding window approach - as you move out of the current window, calculate the new avg and if it is larger than the max, replace it. Code is below, cheers, ACC.


public class Solution
{
    public double FindMaxAverage(int[] nums, int k)
    {
        double sum = 0;
        double avg = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            if (i < k)
            {
                sum += nums[i];
                if (i == k - 1)
                {
                    avg = sum / k;
                }
            }
            else
            {
                sum -= nums[i - k];
                sum += nums[i];
                avg = Math.Max(avg, sum / k);
            }
        }

        return avg;
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons