последовательная возрастающая подпоследовательность

Question

Я пытаюсь найти самую длинную увеличивающуюся последовательную подпоследовательность в списке.

пример: если у меня есть список: [1,2,3,0,2,3,5,6,7,1,4,5,6,9] вывод должен быть [0,2,3,5,6,7], как это больше, чем [1,2,3] и [1,4,5,6,9]

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

Итак, вот мой код, и это один из способов, которым я пытался его реализовать, проблема, с которой я столкнулся, - это добавить temp в arr2. Помогите мне исправить это и предложить альтернативный и более эффективный алгоритм, который я мог бы использовать для этого?

arr = [1,2,3,0,2,3,5,6,7,1,4,5,6,9] #original list 
arr2 = [] #empty list (2 dimension) 
counter = 1 

temp = [] #temporary list 
for x,y in enumerate(arr): 

    if(x == 0): 
     temp.append(y) #append first value to temp 
    else: 

     if(arr[x] > arr[x-1]): #if value of x is greater than previous one: 

      counter += 1 #increase counter if condition met 
      temp.append(y) #append list value to temp 

     else: #if value of x is not greater than previous one: 

      print(temp) 
      arr2.append(temp) #append entire temp list to arr2 
      temp[:] = [] #clear the temp list 
      temp.append(y) #append the new lowest value to temp 
      counter = 1 #reset counter 

print(arr2) 

Answer 1

первых, вы копируете ссылку на список, когда вы пишете:
arr2.append(temp)
И затем обновить список temp, так что вы в конечном итоге с несколько ссылок на тот же список в arr2. Вы должны сделать копию списка вместо:
arr2.append(temp[:])

Кроме того, вы никогда не копировать последние подпоследовательности найденных таким образом вы теряете один в arr2. Вы можете сделать это за пределами петли for, например:

 else: #if value of x is not greater than previous one: 

      print(temp) 
      arr2.append(temp) #append entire temp list to arr2 
      temp[:] = [] #clear the temp list 
      temp.append(y) #append the new lowest value to temp 
      counter = 1 #reset counter 

arr2.append(temp[:]) 
print(arr2) 

С выше, вы получите [[1, 2, 3], [0, 2, 3, 5, 6, 7], [1, 4, 5, 6, 9]] при печати arr2. Тогда это только вопрос выбора самого длинного списка внутри.

Answer 2

Сначала l0 быть данный список:

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

Далее мы создаем список всех смежных подсписков из l0, но мы выбрасываем те, которые не увеличиваются (см if завершение объекта генератора).

l1 = [l[i:j] for i in xrange(len(l)-1) for j in xrange(i,len(l0)) if l[i:j] == sorted(l[i:j])] ## all substrings that are increasing. 

То, что вы просили, является самой длинной такой подстрокой. Так просто возвращаем максимальные длины тех:

print max([len(l) for l in l1]) 

Answer 3

Решение без создания нового списка.

def max_inc_seq(seq): 
    first_ret = first_curr = 0 
    last_ret = last_curr = 0 
    for i in range(1, len(seq)): 
     if seq[i] > seq[i-1]: 
      last_curr = i # move pointer to the item 
     else: 
      last_curr = first_curr = i # reset pointers 
     len_curr = last_curr - first_curr 
     len_ret = last_ret - first_ret 
     if len_curr > len_ret: # the current seq. longer what longest for now 
      first_ret = first_curr 
      last_ret = last_curr    
    return seq[first_ret:last_ret+1] 

Тесты для max_inc_seq:

seqs = (
    ([0, 1, 2], [0, 1, 2]), 
    ([1,2,3,0,2,3,5,6,7,1,4,5,6,9], [0, 2, 3, 5, 6, 7]), 
    ([1, 0], [1]), 
    ([-1, 0, 1], [-1, 0, 1]), 
    ([0, 1, 1], [0, 1]), 
    ) 

for seq, test in seqs: 
    ret = max_inc_seq(seq) 
    assert ret == test, "{} != {}".format(ret, test) 

Answer 4

Это наиболее эффективный алгоритм для рассматриваемой задачи. Он имеет временную сложность O(N) и сложность пространства O(1).

• Итерация с начала массива.

• Проверьте, является ли следующий элемент больше, чем текущий элемент. Если да, то увеличивайте конечную позицию массива. Затем проверьте, лучше ли эта длина, чем максимальная длина всего времени до сих пор. Если да, то инициализируйте beststart и bestend с текущим началом и концом соответственно.

• Если следующий элемент не больше текущего элемента, затем повторно инициализируйте начальную и конечную позиции.

Вот простая реализация вышеприведенного алгоритма:

arr = [1,2,3,0,2,3,5,6,7,1,4,5,6,9] #original list 

l = len(arr) # l stores the length of the array 
i = 0 # initialize i, iterate from left of the array 

max = 1 # the max is always a one element array 

start = 0 # initialize start at the beginning of the array 
end = 0 # initialize end at the beginning of the array 

beststart = 0 # initialize beststart at the beginning of the array 
bestend = 0 # initialize bestend at the beginning of the array 

while i<l: 
    if i+1 < l and arr[i+1]>arr[i]: 
     end = end + 1 # increment end, as we found a longer array 
     if (end-start+1) > max: 
      max = (end - start + 1) # update max 
      beststart = start # update beststart as we have the longest array till this point 
      bestend = end # update bestend as we have the longest array till this point 
    else: 
     start = i+1 # re-initialize start 
     end = i+1 # re-initialize end 

    i = i + 1 

print (arr[beststart:bestend+1]) # print the longest array 

Выход: [0, 2, 3, 5, 6, 7]