643. Maximum Average Subarray I

leetcode easy

#array#csharp#easy#leetcode#math#search#sliding-window

Task

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4

Output: 12.75000

C# solution

matched/original

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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double FindMaxAverage(vector<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.size(); i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        return (double)maxSum / k;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

var findMaxAverage = function(nums, k) {
    let currentSum = 0;
    for (let i = 0; i < k; i++) {
        currentSum += nums[i];
    }
    let maxSum = currentSum;
    
    for (let i = k; i < nums.length; i++) {
        currentSum += nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum / k;
};

Python solution

matched/original

def findMaxAverage(nums, k):
    current_sum = sum(nums[:k])
    max_sum = current_sum
    
    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, current_sum)
    
    return max_sum / k

Go solution

matched/original

package main

func findMaxAverage(nums []int, k int) float64 {
    currentSum := 0
    for i := 0; i < k; i++ {
        currentSum += nums[i]
    }
    maxSum := currentSum
    
    for i := k; i < len(nums); i++ {
        currentSum += nums[i] - nums[i - k]
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    
    return float64(maxSum) / float64(k)
}

Explanation

Algorithm

Инициализация скользящего окна

Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.

Перемещение окна

Перемещайте окно длиной k по массиву, добавляя следующий элемент и убирая предыдущий, чтобы поддерживать сумму текущего окна.

Обновление максимальной суммы

На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎