Наибольшая невозрастающая подпоследовательность
Михаил Попов 10.12.2015 15:38 Python , Алгоритмы 1 комментарийПродолжаю цикл разбора алгоритмов по курсу, который я проходил на stepic.org. Сегодня рассмотрим достаточно сложную задачу.
Дано целое число 1≤n≤105 и массив A[1...n], содержащий неотрицательные целые числа, не превосходящие 109. Найдите наибольшую невозрастающую подпоследовательность в A. В первой строке выведите её длину k, во второй — её индексы 1≤i1<i2<…<ik≤n (таким образом, A[i1]≥A[i2]≥…≥A[in])
Sample Input: 5 5 3 4 4 2 Sample Output: 4 1 3 4 5
Решение этой задачи методом динамического программирования со временем исполнения O(n2) я написал достаточно быстро, и алгоритм решения на Python выглядит так:
def main():
# Прочитаем исходные данные из консоли
n = int(input())
arr = [int(i) for i in input().split(' ')]
# Создадим вспомогательный список, в котором будем хранить решения
lds = [1]*(n)
# В цикле посчитаем с конца, сколько элементов подпоследовательности являются невозрастающими
# Нам нужно выполнить расчет для каждого элемента последовательности, т.е. время решения O(n^2)
for i in range(n - 2, -1, -1):
for j in range(n - 1, i, -1):
if arr[i] >= arr[j] and lds[i] < lds[j] + 1:
lds[i] = lds[j] + 1
# Выведем максимальный элемент, это будет количество элементов в подпоследовательности
print(max(lds))
# Восстановим решение по рассчитанным данным
for i in range(n):
if lds[i] == max_lds:
print(i + 1, end=' ')
max_lds = max_lds - 1
if __name__ == "__main__":
main()
Однако это решение не удалось сдать, т.к. при числах, приближающимся к 109 алгоритм начинал работать непозволительно долго. Требовалось найти решение, которое работает быстрее.
Пришлось немного погуглить и решение с временем работы - O(nlogn) нашлось. Для решения моей задачи алгоритм из статьи понадобилось немного модифицировать.
Я сделал реверс заданной последовательности, а также добавил увеличение значения минимума при x[M[mid]]=x[i].
Вот такой пример решения на Python у меня получился:
def longest_subseq():
# Прочитаем исходные данные из консоли
n = int(input())
x = [int(i) for i in input().split(' ')]
P = [0]*n
M = [0]*(n + 1)
L = 0
x = x[::-1]
for i in range(n):
lo = 1
hi = L
while lo <= hi:
mid = (lo + hi) // 2
if x[M[mid]] < x[i]:
lo = mid + 1
elif x[M[mid]] == x[i]:
lo += 1
else:
hi = mid - 1
newL = lo
P[i] = M[newL - 1]
if newL > L:
M[newL] = i
L = newL
elif x[i] < x[M[newL]]:
M[newL] = i
# Восстановим решение по рассчитанным данным
re = [0]*L
k = M[L]
for i in range(L-1, -1, -1):
re[i] = n - k
k = P[k]
print(len(re))
print(' '.join(map(str,re[::-1])))
if __name__ == "__main__":
longest_subseq()
Наверно можно оптимизировать это решение, не выполняя реверс, но кажется от этого алгоритм потеряет наглядность, так как нужно будет выполнять обратный цикл и сравнивать элементы немного иначе.
Как закодировать строку с помощью алгоритма Хаффмана | Новый раздел по алгоритмам |
0 0 |