Вот алгоритм во O(n lg k) времени, где n - длина массива, а k - длина максимального подмассива, имеющего 2 * min > max.
Пусть A массив. Давайте начнем со следующего инварианта: для j между 0 и length A, SA(j) пусто или 2 * min > max. Инициализировать чрезвычайно легко: возьмите пустой подмассив из индексов от 0 до 0. (Обратите внимание, что SA(j) может быть пустым, потому что A[j] может быть нулевым или отрицательным: у вас нет 2 * min > max, потому что min >= 2 * min > max невозможно .)
Алгоритм: для каждого j мы устанавливаем SA(j) = SA(j-1) + A[j]. Но если A[j] >= 2 * min(SA(j-1)), то инвариант нарушается. Чтобы восстановить инвариант, мы должны удалить все элементы e из SA (j), которые встречают A[j] >= 2 * e. Таким же образом инвариант нарушается, если 2 * A[j] <= max(SA(j-1)). Чтобы восстановить инвариант, мы должны удалить все элементы e из SA(j), которые встречают 2 * A[j] <= e.
. На лету мы отслеживаем самый длинный найденный SA(j) и возвращаем его.
Отсюда и алгоритм:
SA(0) <- A[0..1] # 1 excluded -> empty subarray
ret <- SA(0)
for j in 1..length(A):
if A[j] >= 2 * min(SA(j-1)):
i <- the last index having A[j] >= 2 * A[i]
SA(j) <- A[i+1..j+1]
else if 2 * A[j] <= max(SA(j-1)):
i <- the last index having 2 * A[j] <= A[i]
SA(j) <- A[i+1..j+1]
if length(SA(j)) > length(ret):
ret <- SA(j)
return ret
Вопрос: как нам найти последний индекс i, имеющий A[j] >= 2 * A[i]? Если мы перебираем SA(j-1), нам нужно не более k шагов, и тогда сложность времени будет O(n k) (мы начнем с j-1 и ищем последнее значение, которое сохраняет инвариант).
Но есть лучшее решение. Представьте, что у нас есть минимальная куча, в которой хранятся элементы SA(j-1) вместе с их позициями. Первый элемент - это минимум SA(j-1), пусть i0 будет его индексом. Мы можем удалить все элементы с начала SA(j-1) до i0 включительно. Теперь мы уверены, что A[j] >= 2 * A[i] для всех оставшихся i с? Нет: может быть, есть еще элементы, которые являются маленькими. Следовательно, мы удаляем элементы один за другим, пока не будет восстановлен инвариант.
Нам потребуется максимальная куча, чтобы справиться с другой ситуацией 2 * A[j] <= max(SA(j-1)).
Чем проще создать ad ho c очередь, которая имеет следующие операции:
- add (v): добавить элемент
v в очередь - remove_until_min_gt ( v): удалять элементы из начала очереди до тех пор, пока минимум не станет больше
v - remove_until_max_lt (v): удалить элементы из начала очереди до тех пор, пока максимум не станет меньше
v - максимум: получить максимум из очереди
- минимум: получить минимум из очереди
С двумя кучами maximum и minimum равны O(1), но другие операции: O(lg k).
Вот реализация Python, в которой хранятся индексы начала и конца очереди:
import heapq
class Queue:
def __init__(self):
self._i = 0 # start in A
self._j = 0 # end in A
self._minheap = []
self._maxheap = []
def add(self, value):
# store the value and the indices in both heaps
heapq.heappush(self._minheap, (value, self._j))
heapq.heappush(self._maxheap, (-value, self._j))
# update the index in A
self._j += 1
def remove_until_min_gt(self, v):
return self._remove_until(self._minheap, lambda x: x > v)
def remove_until_max_lt(self, v):
return self._remove_until(self._maxheap, lambda x: -x < v)
def _remove_until(self, heap, check):
while heap and not check(heap[0][0]):
j = heapq.heappop(heap)[1]
if self._i < j + 1:
self._i = j + 1 # update the start index
# remove front elements before the start index
# there may remain elements before the start index in the heaps,
# but the first element is after the start index.
while self._minheap and self._minheap[0][1] < self._i:
heapq.heappop(self._minheap)
while self._maxheap and self._maxheap[0][1] < self._i:
heapq.heappop(self._maxheap)
def minimum(self):
return self._minheap[0][0]
def maximum(self):
return -self._maxheap[0][0]
def __repr__(self):
ns = [v for v, _ in self._minheap]
return f"Queue({ns})"
def __len__(self):
return self._j - self._i
def from_to(self):
return self._i, self._j
def find_min_twice_max_subarray(A):
queue = Queue()
best_len = 0
best = (0, 0)
for v in A:
queue.add(v)
if 2 * v <= queue.maximum():
queue.remove_until_max_lt(v)
elif v >= 2 * queue.minimum():
queue.remove_until_min_gt(v/2)
if len(queue) > best_len:
best_len = len(queue)
best = queue.from_to()
return best
Вы можете видеть, что каждый элемент A кроме последнего может проходить через эту очередь, таким образом, O(n lg k) сложность времени. * 1 090 *
Вот тест.
import random
A = [random.randint(-10, 20) for _ in range(25)]
print(A)
# [18, -4, 14, -9, 8, -6, 12, 13, -7, 7, -2, 14, 7, 9, -9, 9, 20, 19, 14, 13, 14, 14, 2, -8, -2]
print(A[slice(*find_min_twice_max_subarray(A))])
# [20, 19, 14, 13, 14, 14]
Очевидно, что если бы был способ найти начальный индекс, который восстанавливает инвариант в O(1), мы бы имели временную сложность в O(1). (Это напоминает мне, как алгоритм KMP находит лучший новый старт в проблеме сопоставления строк, но я не знаю, возможно ли создать что-то подобное здесь.)