644. Maximum Average Subarray II

leetcode hard

#array#csharp#hard#leetcode#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 currSum = nums.Take(k).Sum();
        int maxSum = currSum;
        for (int i = k; i < nums.Length; i++) {
            currSum += nums[i] - nums[i - k];
            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        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 currSum = nums.Take(k).Sum();
        int maxSum = currSum;
        for (int i = k; i < nums.size(); i++) {
            currSum += nums[i] - nums[i - k];
            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        return (double)maxSum / k;
    }
}

Java solution

matched/original

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int currSum = 0;
        for (int i = 0; i < k; i++) {
            currSum += nums[i];
        }
        int maxSum = currSum;
        for (int i = k; i < n; i++) {
            currSum += nums[i] - nums[i - k];
            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        return maxSum / (double) k;
    }
}

JavaScript solution

matched/original

var findMaxAverage = function(nums, k) {
    let currSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
    let maxSum = currSum;
    for (let i = k; i < nums.length; i++) {
        currSum += nums[i] - nums[i - k];
        if (currSum > maxSum) {
            maxSum = currSum;
        }
    }
    return maxSum / k;
};

Python solution

matched/original

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

Go solution

matched/original

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

Explanation

Algorithm

Используйте скользящее окно длины k для нахождения начального среднего значения.

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

Следите за максимальным средним значением и верните его после проверки всех возможных окон.

😎