Возможно, более простое решение O (n) для поиска подмассива длины K (или более) с максимальным средним

Я видел этот вопрос на сайте конкурса кодирования.

Предположим, вам дан массив из n целых чисел и целое число k (n‹= 10^5, 1‹=k‹=n). Как найти подмассив (непрерывный) с максимальным средним значением, длина которого больше k.

В исследовательских работах (arxiv.org/abs/cs/0207026.) представлено решение O(n), связанное с дубликатом SO вопрос. Я отправляю это как отдельный вопрос, так как думаю, что у меня есть аналогичный метод с более простым объяснением. Как вы думаете, что-то не так с моей логикой в ​​​​решении ниже?

Вот логика:

1. Начните с диапазона окна как [i,j] = [0,K-1]. Затем переберите оставшиеся элементы.
2. Для каждого следующего элемента j обновите сумму префикса**. Теперь у нас есть выбор — мы можем использовать весь диапазон [i,j] или отбросить диапазон [i:j-k] и оставить [j-k+1:j] (т.е. оставить последние K элементов). Выберите диапазон с более высоким средним значением (используйте сумму префикса, чтобы сделать это за O (1)).
3. Следите за максимальным средним значением на каждом этапе
4. Вернуть максимальное среднее значение в конце

** Я вычисляю сумму префикса при переборе массива. Сумма префикса в я представляет собой кумулятивную сумму первых i элементов в массиве.

Код:

def findMaxAverage(nums, k):
    prefix = [0]
    for i in range(k):
        prefix.append(float(prefix[-1] + nums[i]))
    mavg = prefix[-1]/k
    lbound = -1
    for i in range(k,len(nums)):
        prefix.append(prefix[-1] + nums[i])
        cavg = (prefix[i+1] - prefix[lbound+1])/(i-lbound)
        altavg = (prefix[i+1] - prefix[i-k+1])/k
        if altavg > cavg:
            lbound = i-k
            cavg = altavg
        mavg = max(mavg, cavg)

    return mavg