Найти самую длинную подпоследовательность в массиве

Question

Проблема заключается в том, чтобы найти длину самой длинной подпоследовательности из входного массива таким образом, чтобы все элементы находились в отсортированном порядке.

Пример: ввод =>[10,22,9,33,21,50,41,60,80]

Пример: Выход =>[10,22,33,50,60,80] является

Моя попытка:

def longest_sequence(input): 
    obj = [] 
    for x in sorted(input): 
     obj.append(x) 
    print[obj, len(obj)] 
    # [[9, 10, 21, 22, 33, 41, 50, 60, 80], 9] 

longest_sequence([10,22,9,33,21,50,41,60,80]) 

Answer 1

import bisect 

def lis(xs): 
    ret = [] 
    for x in xs: 
     i = bisect.bisect_left(ret, x) 
     ret[i:i+1] = x, 
    return len(ret) 

Пример:

>>> lis([10, 1, 2, 3]) 
3 
>>> lis([10,22,9,33,21,50,41,60,80]) 
6 

ПРИМЕЧАНИЕ В приведенном выше коде, ret не содержит действительный подпоследовательности. Но длина правильная. Используйте приведенный выше код, что вы хотите, это только длина LIS.

Объяснение:

Подумайте о [10,22,9,11]. Могут быть два LIS: [10,22], [9,11]. ret в приведенной выше функции lis поддерживает следующее условие:

• ret сортируется; может использовать двоичный поиск (bisect.bisect_left)
• ret[i] содержит минимальное последнее значение для длины - i подпоследовательность.
• ret изменяется ... (учитывая [10,22,9,11] в качестве входных данных)
  • [10] - после обработки 1-й элемент
  • [10, 22] - после обработки 2-го элемента
  • [9, 22] - ... Теперь минимальное значение для 1-подпоследовательности равно 9! 10 перезаписывается.
  • [9, 11]

Сложность Время: О (пк) где п есть число элемента списка, к длина ЛИС.

UPDATE

Модифицированная версия, что правильно получить подпоследовательности:

import bisect 

def lis(xs): 
    if not xs: return [] 
    prev = {} 
    ret = [] 
    for x in xs: 
     i = bisect.bisect_left(ret, x) 
     ret[i:i+1] = x, 
     prev[x] = ret[i-1] if i > 0 else None 
    subseq = [ret[-1]] 
    while subseq[-1] is not None: 
     subseq.append(prev[subseq[-1]]) 
    return list(reversed(subseq[:-1])) 

Пример:

>>> lis([]) 
[] 
>>> lis([10, 1, 2, 3]) 
[1, 2, 3] 
>>> lis([10,22,9,33,21,50,41,60,80]) 
[10, 22, 33, 41, 60, 80] 
>>> lis([1,5,2,6,3,4]) 
[1, 2, 3, 4] 
>>> lis([100,200,1,2,3]) 
[1, 2, 3] 

Answer 2

data = [100,1,2,3] 

conformed = [] 

for i in range (0, len(data)): 
    if i == 0: 
     if data[1]<data[0]: 
     conformed.append(data[1]) 
     else: 
     conformed.append(data[0]) 
    else: 
     if data[i] > data[i-1]: 
      conformed.append(data[i]) 

print conformed, len(conformed)