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 1:

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

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= k <= n <= 105
  • -104 <= nums[i] <= 104

Solution

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        var max = (double) Integer.MIN_VALUE;
        var sum = 0;
        // read in the first k - 1 numbers
        for (var i = 0; i < k - 1; i++) {
            sum += nums[i];
        }
        for (var i = k - 1; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(sum / (double) k, max);
            // clean slate for the next iteration
            sum -= nums[i - (k - 1)];
        }
        return max;
    }
}

Recent posts from blogs that I like

Painting and Photography: Is it art?

Degas' photos of women bathing, Gérôme supporting photography as a fine art, Pierre Bonnard's snaps of Marthe, and the extreme realism of Ellen Altfest.

via The Eclectic Light Company

How often do LLMs snitch? Recreating Theo's SnitchBench with LLM

via Simon Willison

The virtue of unsynn

via fasterthanlime