Как рассчитать максимальную медиану в массиве

Question

Это вопрос алгоритма:

Входные данные - это массив с недвойственными положительными целыми числами. Найдите непрерывный подмассив (размер> 1), который имеет максимальное значение медианы.

Пример: ввод: [100, 1, 99, 2, 1000], вывод должен быть результатом (1000 + 2) / 2 = 501

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

Кто-нибудь имеет лучшую идею, чтобы решить этот вопрос?

Answer 1

tl; dr - Мы можем показать, что ответ должен иметь длину 2 или 3, после чего наступает линейное время для проверки всех возможностей.

Допустим, входное значение равно A, а наименьший подмассивс самой большой медианой - a.Самая большая медиана - это либо отдельный элемент, либо среднее значение пары элементов из a.Обратите внимание, что каждый элемент в a больше, чем самый большой элемент медианы, может находиться только рядом с элементами, меньшими, чем самый маленький элемент медианы (в противном случае такую ​​пару можно было бы выбрать в качестве подмассива для формирования большей медианы).

Если на любом конце a есть пара элементов, которые не содержат элемент медианы, его можно исключить из a, не затрагивая медиану, противоречие.

Если бы любой конец a был меньше, чем наименьший элемент медианы, его удаление увеличило бы медиану, противоречие.

Таким образом, каждый конец a является либо элементом медианы, либо больше, чем самый большой элемент медианы (потому что он больше, чем самый маленький эльт медианы и не равен наибольшему эльту медианы).).

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

Если a нечетно, то оно должно иметь длину три, так как любая большая нечетная длина может иметь 2, удаленные от конца a, наиболее удаленного от медианы, без изменения медианы.

Если a четное, то оно должно иметь длину 2, потому что любая большая четная длина, записанная элементами медианы с элементами интерьера, чередующимися между меньшим и большим, чем медиана, должна иметь один из медианных элементов, смежный с большим элементом, чемдругой эльт медианы, образующий большую медиану.

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

Учитывая это, проверять каждый такой подмассив за линейное время.О (п).

Answer 2

Это реализация Python алгоритма, который решает проблему в O(n):

import random
import statistics

n = 50
numbers = random.sample(range(n),n)

max_m = 0;
max_a = [];

for i in range(2,3):
    for j in range(0,n-i+1):
        a = numbers[j:j+i]
        m = statistics.median(a)
        if m > max_m:
            max_m = m
            max_a = a

print(numbers)
print(max_m)
print(max_a)

Это разновидность алгоритма грубой силы (O (n ^ 3)), который выполняет поиск только подмассивов длиной 2 или 3. Причина в том, что для каждого массива размером n существует под-массив с такой же или улучшенной медианой. Применяя эти рассуждения рекурсивно, мы можем уменьшить размер подмассива до 2 или 3. Таким образом, рассматривая только подмассивы размера 2 или 3, мы гарантированно получим подмассив с максимальной медианой.

Операция следующая: если для смежного подмассива (в начале или в конце) хотя бы половина элементов ниже, чем медиана (или ниже, чем оба значения, образующие медиану, если это это так), удалите их, чтобы улучшить или хотя бы сохранить медиану.

Если во всех подмассивах всегда есть хотя бы еще один элемент выше или равный медиане (ам), чем ниже, наступит момент, когда размер подмассива будет равным медиане. В этом случае это означает, что комплемент будет иметь больше элементов ниже медианы, и, таким образом, мы можем просто удалить комплемент и улучшить (или сохранить) медиану. Таким образом, мы всегда можем выполнить операцию. Для n=3 может случиться так, что вам потребуется удалить 2 или 3 элемента для выполнения операции, что недопустимо. В этом случае результатом является сам список.