Java | LeetCode
Задача: 643. Maximum Average Subarray I
Сложность: easy
Вам дан целочисленный массив 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⃣Обновление максимальной суммы
На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.
😎 Решение:
public class Solution {
public double findMaxAverage(int[] nums, int k) {
int currentSum = 0;
for (int i = 0; i < k; i++) {
currentSum += nums[i];
}
int maxSum = currentSum;
for (int i = k; i < nums.length; i++) {
currentSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, currentSum);
}
return (double) maxSum / k;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 512 ·