Условие

Дан массив nums длины n и целое число k. Найдите подмассив длины k с максимальным средним значением и верните это значение.

Примеры

Input: nums = [1, 12, -5, -6, 50, 3], k = 4 Output: 12.75000 Explanation: Подмассив [12, -5, -6, 50] имеет максимальное среднее значение (12.75).

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

Решение

fun findMaxAverage(nums: IntArray, k: Int): Double {
    var sum = 0.0
    // Инициализируем сумму первых k элементов
    for (i in 0 until k) {
        sum += nums[i]
    }

    var maxSum = sum // Максимальная сумма на текущий момент

    // Сканируем массив, используя скользящее окно
    for (i in k until nums.size) {
        sum += nums[i] - nums[i - k] // Добавляем новый элемент и убираем старый
        if (sum > maxSum) {
            maxSum = sum // Обновляем максимальную сумму
        }
    }

    return maxSum / k // Возвращаем среднее значение
}

Временная сложность

O(n), где n — длина массива, так как массив перебирается один раз.

Пространственная сложность

O(1), так как не используется дополнительная память.