Ошибка в коде задачи о самой длинной возрастающей подпоследовательности
Самая Длинная Возрастающая Подпоследовательность
Самая длинная задача увеличения подпоследовательности состоит в том, чтобы найти подпоследовательность заданной последовательности, в которой элементы подпоследовательности находятся в отсортированном порядке и в которой подпоследовательность максимально длинна
Я пытаюсь реализовать программу для Самая Длинная Возрастающая Подпоследовательность, Он дает правильный вывод для некоторых входных паттернов, но для некоторых дает неправильный результат. Кто-нибудь может сказать мне, где ошибка в коде.
Что я уже пробовал:
Вот мой код
def binary_search(t, l, r, key): while (r - l > 1): m = l + (r - l)//2 if (t[m]>=key): r = m else: l = m return r def LIS(): tailTable = [0] * N tailTable[0] = lst[0] len = 1 for i in range(1, N): if (lst[i] < tailTable[0]): # New Smallest Value tailTable[0] = lst[i] elif (lst[i] > tailTable[len - 1]): # lst[i] wants to extend largest subsequence tailTable[len] = lst[i] len += 1 else: # A[i] wants to be current end candidate of an existing # subsequence. tailTable[binary_search(tailTable, -1, len-1, lst[i])] = lst[i] return len if __name__ == "__main__": N = int(input()) lst = [] for i in range(N): lst.append(input()) ret = LIS() print(ret)
Patrice T
Дайте пример ввода, который даст неправильный результат.