Maximum Average Subarray I

Problem statement

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.

Example:

Input:

nums = [1,12,-5,-6,50,3], k = 4

Expected output:

12.75000

Explanation: Subarray [12,-5,-6,50] has the maximum average 51 / 4 = 12.75.

If you would like to solve the problem on LeetCode, here is the link to the problem: LeetCode problem link

Golang Solution

Use a fixed-size sliding window of length k. Track the window sum, slide one step at a time by removing the leftmost element and adding the next element, and keep the maximum sum. The answer is that maximum sum divided by k.

Time: O(n)
Space: O(1)

func findMaxAverage(nums []int, k int) float64 {
	maxSoFar := 0

	if len(nums) < k {
		return 0
	}

	for i := 0; i < k; i++ {
		maxSoFar += nums[i]
	}

	curr := maxSoFar
	var i int
	for j := k; j < len(nums); j++ {
		curr -= nums[i]
		curr += nums[j]

		if curr > maxSoFar {
			maxSoFar = curr
		}
		i += 1
	}

	return float64(maxSoFar) / float64(k)
}