Задача: 643. Maximum Average Subarray I
Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
👨💻 Алгоритм:
1⃣Инициализация скользящего окна
Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.
2⃣Перемещение окна
Перемещайте окно длиной k по массиву, добавляя следующий элемент и убирая предыдущий, чтобы поддерживать сумму текущего окна.
3⃣Обновление максимальной суммы
На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.
😎 Решение:
function findMaxAverage($nums, $k) {
$currentSum = array_sum(array_slice($nums, 0, $k));
$maxSum = $currentSum;
for ($i = $k; $i < count($nums); $i++) {
$currentSum += $nums[$i] - $nums[$i - $k];
$maxSum = max($maxSum, $currentSum);
}
return $maxSum / $k;
}👉Новости 👉Платформа