Блог

Учитывая массив целых чисел, как мы можем сгенерировать все возрастающие подпоследовательности так, чтобы все они имели одинаковую длину?

Пример: учитывая этот список

 l = [1, 2, 4, 5, 3, 6]
  

Ответ должен быть, если мы рассмотрим подпоследовательности длиной 4:

 [1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 4, 5, 6]
[2, 4, 5, 6]
  

 from itertools import combinations

# the second item of the tuple is the position of the element in the array
zeta = [(1, 1), (2, 2), (4, 3), (5, 4), (3, 5), (6, 6)]
comb = combinations(sorted(zeta, key=lambda x: x[0]), 4)


def verif(x):
    l = []
    for k in x:
        l.append(k[1])
    for i in range(len(l)-1):
        if l[i 1]-l[i] < 0:
            return 0
    return 1


for i in comb:
    if verif(list(i)):
        print(i)
  

Мне нужен лучший подход, такой как решение для динамического программирования, потому что, очевидно, мое решение очень медленное для большего списка целых чисел. Является ли проблема LIS полезной в этой ситуации?