Нахождение непрерывной подпоследовательности, которая минимизирует среднее значение остальной части массива?

Question

Предположим, есть целочисленный массив arr[0..n-1], Найти подпоследовательность sub[i..j] (i > 0 и j

Пример:

arr[5] = {5,1,7,8,2};

Удалить {7,8}массив становится {5, 1, 2} который имеет в среднем 2,67 (наименьшее возможное).

Я думал, что это модификация Longest возрастающей подпоследовательности, но не мог понять это.

Спасибо,

Answer 1

Найдем среднее значение с помощью бинарного поиска.

Предположим, что сумма всех элементов равна S.

Для данного x давайте проверим, существуют ли i и j такие, что avg всех элементов кроме от i до j меньше или равно x.

Чтобы сделать это, давайте вычтем x из всех элементов в arr. Нам нужно проверить, существуют ли i и j такие, что сумма всех элементов, кроме i и j, меньше или равна нулю. Для этого давайте найдем сумму всех элементов в текущем массиве: S' = S - x * n. Итак, мы хотим найти i и j такие, что сумма от i до j будет больше или равна S'. Чтобы сделать это, давайте найдем подмассив с суммой больших сумм. И это можно сделать с помощью элегантного алгоритма Джея Кадана: https://en.wikipedia.org/wiki/Maximum_subarray_problem

Когда прекратить бинарный поиск? При этом максимальная сумма подмассива станет нулевой (или достаточно близкой).

Временная сложность: O(n log w), w - выбор двоичного поиска.