🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 644. Maximum Average Subarray II
Сложность: hard
Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
👨💻 Алгоритм:
1⃣Используйте скользящее окно длины k для нахождения начального среднего значения.
2⃣Перемещайте окно по массиву, добавляя следующий элемент и убирая предыдущий, обновляя текущее среднее значение.
3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон.
😎 Решение:
fun findMaxAverage(nums: IntArray, k: Int): Double {
var currSum = nums.take(k).sum()
var maxSum = currSum
for (i in k until nums.size) {
currSum += nums[i] - nums[i - k]
if (currSum > maxSum) {
maxSum = currSum
}
}
return maxSum.toDouble() / k
}
Ставь 👍 и забирай 📚 Базу знаний
