Самый длинный непрерывный подрамник со средним значением, большим или равным k

Question

Рассмотрим массив из N целых чисел. Найдите самый длинный смежный подмассив, чтобы среднее значение его элементов было больше (или равно), чем заданное число k.

Очевидный ответ имеет сложность O (n^2). Мы можем сделать лучше?

Answer 1

Мы можем уменьшить эту проблему до самого длинного смежного подмассива с суммой> = 0 путем вычитания k из всех значений в O (n) времени. Теперь давайте посчитаем префикс суммы:

index 0  1  2  3  4  5  6 
array   2  -3 3  2  0  -1 
prefix 0  2  -1 2  5  5  4 

Теперь эта проблема состоит в нахождении двух индексов наиболее далеко друг от друга с prefix_right - prefix_left >= 0. Давайте создадим новый префикс-индексный массив и отсортируем его по префиксу, а затем по индексам.

index 2  0  1  3  6  4  5 
prefix -1 0  2  2  4  5  5 

Затем мы можем сделать прямо к левой стреловидности вычислить для каждого префикса, максимальный индекс с префиксом, большим или равным текущему префиксом:

index 2  0  1  3  6  4  5 
prefix -1 0  2  2  4  5  5 
maxind 6  6  6  6  6  5  5 

Теперь, давайте идти вернуться к исходному массиву префикса. Для каждой пары префикс-индекс мы выполняем бинарный поиск в нашем новом массиве, чтобы найти наименьший префикс> = текущий префикс. Мы вычитаем из максимального значения двоичного искомого префикса индекс текущего префикса для получения наилучшей длины последовательности, начиная с текущего индекса. Возьмите последовательность с максимальной длиной.

Этот алгоритм является O (n log n) из-за сортировки и n бинарных поисков.

Answer 2

Мы можем решить проблему в O (n) времени и сложность пространства O (n):
Я попытался с наивным и оптимальным подходом.
Короче говоря, проблема состоит из двух шагов:
(1) Вычесть k из каждого ar [i] и найти кумулятивное значение в новом массиве. Давайте назовем новый массив как cumArr [].
(2) Теперь проблема заключается в нахождении max (j-1) в CumArr [] такой, что j> i и cumArr [j]> cumArr [i]. Этот шаг является известным вопросом и может быть найден во многих местах.

Вот деталь с управлением кодом: http://codeshare.io/Y1Xc8

Там могут быть небольшие случаи угловые, которые могут быть обработаны легко.
Дайте мне знать ваши мысли друзей.