Итеративное решение для нахождения самой длинной возрастающей подпоследовательности с использованием Python

Question

Я пытаюсь реализовать итеративное решение для самой длинной возрастающей подпоследовательности, используя bisect. Моя реализация терпит неудачу в какой-то момент. Помоги мне исправить это.

Реализация:

from bisect import bisect

def lis_iterative(seq):
    buff = []
    for n in seq:
        i = bisect(buff, n)
        if i == len(buff):
            buff.append(n)
        else:
            buff[i] = n
    return buff

def main():
    seq = [43, 25, 6, 37, 27, 26, 7, 24, 457, 5, 22, 72]
    print lis_iterative(seq)

main()

Ожидаемый результат:

[6, 7, 24, 457]

Сгенерированный выход:

[5, 7, 22, 72]

Answer 1

Ваш текущий алгоритм, кажется, не имеет особого смысла, как отмечено в комментарии BrenBarn. Вот что я придумал:

def lis_iterative(seq):
    n = len(seq)
    dp = [(0, -1)]*n
    # dp contains (best, idx) tuples, where best is the length of the longest
    # increasing sequence starting from that element, and idx is the index of the
    # next element in that sequence
    for i in range(n-1, -1, -1):
        best = 0
        idx = -1
        for j in range(i+1, n):
            if seq[i] < seq[j] and dp[j][0] + 1 > best:
                best = dp[j][0] + 1
                idx = j
        dp[i] = (best, idx)

    # find longest increasing sequence from dp, then follow idx chain for result
    result = []
    idx = max(range(n), key=lambda i: dp[i][0])
    while idx != -1:
        result.append(seq[idx])
        _, idx = dp[idx]
    return result