Maximum Average Subarray I

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: dp = selected_real_kind(15, 307) ! double precision

    integer, dimension(:), allocatable :: nums
    integer :: n, k
    real(dp) :: max_avg

    call get_args(n, k)

    allocate(nums(n))

    read(*, *) nums

    max_avg = find_max_avg(nums, n, k)

    write (*, '(F10.5)') max_avg

contains

    function find_max_avg(nums, n, k) result(max_avg)
        implicit none

        integer, intent(in) :: n, k
        integer, dimension(:), intent(in) :: nums
        real(dp) :: max_avg

        integer :: i, j
        real(dp) :: avg

        do i = 1, n - k + 1
            avg = 0.0_dp
            do j = i, i + k - 1
                avg = avg + nums(j)
            end do
            avg = avg / k

            if (abs(avg - max_avg) < 1.0e-5_dp) then
                max_avg = max(avg, max_avg)
            else if (avg > max_avg) then
                max_avg = avg
            end if
        end do

    end function find_max_avg

    subroutine get_args(n, k)
        implicit none

        integer, intent(out) :: n, k

        character(len=100) :: buffer

        read(*, '(A)') buffer
        read(buffer, *) n
        read(*, '(A)') buffer
        read(buffer, *) k

    end subroutine get_args

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaxAverageSubarray
    implicit none

contains

    function max_average_subarray(nums, k) result(max_avg)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        real(kind=8) :: max_avg

        ! Local variables
        integer :: n, i, j
        real(kind=8) :: sum, avg

        ! Initialize variables
        n = size(nums)
        sum = 0.0d0
        avg = 0.0d0
        max_avg = -1.0d0

        ! Loop through the array
        do i = 1, n - k + 1
            ! Calculate the sum of the subarray
            sum = sum(nums(i:i+k-1))

            ! Calculate the average of the subarray
            avg = sum / real(k, kind=8)

            ! Check if the average is greater than the current maximum
            if (avg > max_avg) then
                max_avg = avg
            end if
        end do

        ! Return the maximum average
        return
    end function max_average_subarray
end module MaxAverageSubarray

program test_max_average_subarray
    use MaxAverageSubarray
    implicit none

    ! Test case 1
    integer, parameter :: nums1(4) = [1, 12, -5, -6]
    integer, parameter :: k1 = 4
    real(kind=8), parameter :: expected1 = 12.75000
    call test_case(nums1, k1, expected1)

    ! Test case 2
    integer, parameter :: nums2(1) = [5]
    integer, parameter :: k2 = 1
    real(kind=8), parameter :: expected2 = 5.00000
    call test_case(nums2, k2, expected2)

contains

    subroutine test_case(nums, k, expected)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        real(kind=8), intent(in) :: expected

        ! Calculate the maximum average subarray
        real(kind=8) :: max_avg
        max_avg = max_average_subarray(nums, k)

        ! Check if the answer is correct
        if (abs(max_avg - expected) < 1.0d-5) then
            write (*,*) "Test case passed!"
        else
            write (*,*) "Test case failed!"
        end if
    end subroutine test_case
end program test_max_average_subarray
🌐 Data from online sources 
def findMaxAverage(nums, k):
    n = len(nums)
    sum_ = sum(nums[:k])
    max_avg = sum_ / k
    for i in range(k, n):
        sum_ = sum_ - nums[i - k] + nums[i]
        max_avg = max(max_avg, sum_ / k)
    return max_avg
  1. Initialize the sum with the first k elements of the input array.
  2. Calculate the average by dividing the sum by k and store it in max_avg.
  3. Loop through the input array from index k to the end.
  4. For each element, update the sum by subtracting the element at the left side of the sliding window (with k length) and adding the current element.
  5. Calculate the average again and update the max_avg if the current average is higher than the previous max_avg.
  6. Return max_avg after the loop ends.
🌐 Data from online sources 
double findMaxAverage(vector<int>& nums, int k) {
    int n = nums.size();
    double sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += nums[i];
    }
    double max_avg = sum / k;
    for (int i = k; i < n; ++i) {
        sum = sum - nums[i - k] + nums[i];
        max_avg = max(max_avg, sum / k);
    }
    return max_avg;
}
  1. Initialize the sum with the first k elements of the input array.
  2. Calculate the average by dividing the sum by k and store it in max_avg.
  3. Loop through the input array from index k to the end.
  4. For each element, update the sum by subtracting the element at the left side of the sliding window (with k length) and adding the current element.
  5. Calculate the average again and update the max_avg if the current average is higher than the previous max_avg.
  6. Return max_avg after the loop ends.