Извлечение подпоследовательности максимальной длины из последовательности [PYTHON]

Question

У меня есть последовательность значений [1,2,3,4,1,5,1,6,7], и мне нужно найти самую длинную подпоследовательность увеличивая длину. Тем не менее, функция должна останавливать подсчет, как только она достигает числа ниже предыдущего. Ответ в этой последовательности в этом случае [1,2,3,4]. Поскольку перед сбросом он имеет 4 значения. Как я могу написать код Python для этого?

Примечание: поиск «самой длинной возрастающей подпоследовательности» представляется общей проблемой, поэтому поиск в Интернете я нахожу много решений, которые будут учитываться для всей длины последовательности, и возвращать подпоследовательность возрастающих значений, игнорируя любые уменьшается, поэтому в этом случае он вернется [1,2,3,4,5,6,7]. Это не то, что я ищу.

Нужно подсчитать каждую подпоследовательность и сбросить счет, достигнув числа ниже предыдущего. Затем нужно сравнить все подсчитанные подпоследовательности и вернуть самый длинный.

Заранее спасибо.

Answer 1

b = [4,1,6,3,4,5,6,7,3,9,1,0] 

def findsub(a): 
    start = -1 
    count = 0 
    cur = a[0] 
    for i, n in enumerate(a): 
    if n is cur+1: 
     if start is -1: 
     start = i - 2 
     count=1 
     count+=1 
     cur = n 
    if n < cur and count > 1: 
     return [a[j] for j in range(start,start+count+1)] 


print findsub(b) 

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

немного лучше выглядит пути, потому что мне не нравится, что:

b = [1,2,0,1,2,3,4,5] 

def findsub(a): 
    answer = [a[0]] 
    for i in a[1:]: 
    if answer[-1] + 1 is i: 
     answer.append(i) 
    if not len(answer) > 1: 
     answer = [i] 
    elif i < answer[-1] and len(answer) > 1: 
     return answer 
    return answer 



print findsub(b) 

Answer 2

Вам необходимо сделать следующее:

1. Создайте функцию W, что данный список, возвращает индекс последнего элемента, который не сильно увеличивается с самого начала списка.

   • К примеру, учитывая следующие списки: [1,2,3,4,1,2,3], [4,2,1], [5,6,7,8], он должен вернуть 4, 1, 4, соответственно, для каждого списка

2. Создать переменную maxim и установите значение 0

3. Повторно делайте следующее до тех пор, пока ваш список не будет
   • Обратитесь к функции W в списке, и назовём возвращаемое значение x
   • если x больше maxim
     • установить maxim в x
     • На данный момент, если вы хотите сохранить эту последовательность, вы можете использовать list-slice notation, чтобы получить ту часть вашего списка, которая содержит последовательность.
   • удалить ту часть вашего списка из списка

Наконец, печать maxim и если вы хранили части вашего списка, содержащего самую длинную последовательность, а затем распечатать последний, который вы получили

Answer 3

Рассмотрите функцию, которая генерирует все возможные восходящие подпоследовательности, вы начинаете с пустого списка, добавляете элементы до тех пор, пока один элемент не будет меньше (или равен?) Предыдущего, после которого вы сохраняете (yield) подпоследовательность и r estart с новой подпоследовательностью.

Одна реализации с использованием генератора может быть таким:

def all_ascending_subsequences(sequence): 
    #use an iterator so we can pull out the first element without slicing 
    seq = iter(sequence) 

    try: #NOTE 1 
     last = next(seq) # grab the first element from the sequence 
    except StopIteration: # or if there are none just return 
     #yield [] #NOTE 2 
     return 

    sub = [last] 
    for value in seq: 
     if value > last: #or check if their difference is exactly 1 etc. 
      sub.append(value) 
     else: #end of the subsequence, yield it and reset sub 
      yield sub 
      sub = [value] 
     last = value 

    #after the loop we send the final subsequence 
    yield sub 

две заметки о обработке пустых последовательностей:

1. закончить генератор StopIteration должен быть поднято таким образом, мы могли бы просто пусть один из next(seq) propegate out - однако, когда from __future__ import generator_stop находится в , это может вызвать RuntimeError, чтобы быть в будущем совместимым. need t o поймать его и явно return.
2. Как я написал, он передает пустой список в . all_ascending_subsequences не генерирует никаких значений, что может быть неточным . Не стесняйтесь расколоть yield [] на сгенерировать пустой список при пустом списке.

Тогда вы можете просто получить самый длинный по телефону max на результат с key=len

b = [1,2,3,4,1,5,1,6,7] 

result = max(all_ascending_subsequences(b),key=len) 
print("longest is", result) 

#print(*all_ascending_subsequences(b))