Как найти положительную подпоследовательность наибольшей длины?

Question

Не могу понять, как это сделать:
Запросить у пользователя размер массива. Задать длину динамического массива. Запросить и считать данные массива у пользователя. Дана последовательность чисел: а1, а2, …, аN. Найти положительную подпоследовательность наибольшей длины.

a= int(input())
xyz=[]
for i in range (a):
    xyz.append(x)

dlina_xyz = len(xyz)

numbers= []
for i in range(a):
    1 =[]
    for j in range(i+1, a):
        if xyz[j]>0:
            1.append(xyz[j])
        else:
            numbers.append(1)
            break

print(numbers.sort(key=len)[0])

Я думаю, что ошибка в том, что у меня будет выводить не наибольшую длину.

Но как это сделать ?

Думаю, нужно получить все последовательности, проверить их на наличие отрицательных числел, и отсортировать по длине, выбирая максимально длинную.

Answer 1

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

max_len=0
for i in range(len(x)):
    c_len=0
    for j in range(i,len(x)):
        if x[j]>0:
            c_len=c_len+1
        else:
            break
    if c_len>max_len:
        max_len=c_len
        max_ind=i
print (max_len, max_ind)

Например, при x=[0,1,2,3,-2,0,1,2,3,4,0,-1,-1,1,2,3,4,5,6,7,8,-3]
имеем:

8 13

По мотивам идей уважаемого @MaxU о вычислительной сложности, внес некоторые модификации в первоначальную версию:

max_len=0
i=0
while i< len(x):
    print (i)
    c_len=0
    for j in range(i,len(x)):
        if x[j]>0:
            c_len=c_len+1
        else:
            break
    if c_len>max_len:
        max_len=c_len
        max_ind=i
    if c_len==0:
        i=i+1
    else:
        i=i+c_len

Результаты работы на моих данных:

8 13

Результат работы на примере @MaxU:

4 8

Answer 2

Вариант решения со многими операторами if, но зато с алгоритмической сложностью O(n) (требуется один проход по списку), и расходом памяти O(5):

def get_longest_pos_seq(arr):
    start_idx, stop_idx, max_len, counter, tmp = 0, 0, 0, 0, 0
    for i in range(1, len(arr)):
        if arr[i-1] <= 0 and arr[i] > 0:
            tmp = i
        if arr[i-1] > 0:
            if arr[i] > 0:
                counter += 1
            if arr[i] <= 0 or i == len(arr) - 1:
                if counter > max_len:
                    max_len = counter
                    start_idx = tmp
                    stop_idx = i + 1 if i == len(arr) - 1 else i
                counter = 0
    return arr[start_idx:stop_idx], start_idx, stop_idx

проверка:

In [61]: arr = [-5, 1, 2, -6, 2, 4, 5, -12, 2, 5, 6, 7]

In [62]: res, start_idx, stop_idx = get_longest_pos_seq(arr)

In [63]: res
Out[63]: [2, 5, 6, 7]

In [64]: start_idx
Out[64]: 8

In [65]: stop_idx
Out[65]: 12

Answer 3

def longest_pos_subarr(arr):
    res_length = 0
    res_start = 0

    for i in range(len(arr)):
        curr_length = 0
        curr_start = i

        while i < len(arr) and arr[i] > 0:
            curr_length += 1
            i += 1

        if curr_length > res_length:
            res_length = curr_length
            res_start = curr_start

    return (res_start, res_length)


arr = [-5, 1, 2, -6, 2, 4, 5, -12, 2, 5, 6, 7]

start, length = longest_pos_subarr(arr)

print(arr[start:start + length])

Answer 4

Оба варианта имеют алгоритмическую сложность O(n).

Вариант №1

arr = [-5, 1, 2, -6, 2, 4, 5, -12, 2, 5, 6, 7]

max_subseq = []
tmp_subseq = []
for num in arr:
    if num > 0:
        tmp_subseq.append(num)
    else:
        max_subseq = max(max_subseq, tmp_subseq, key=len)
        tmp_subseq = []
# Дополнительная проверка нужна на случай, если
# последнее число положительное        
max_subseq = max(max_subseq, tmp_subseq, key=len)
print(max_subseq)

Вариант №2

Тоже самое можно записать короче в ущерб эффективности. Эффективность будет снижена по следующим причинам:

tmp_subseq + [num] - на каждое положительное число создаётся список [num], затем два списка объединяются.
max(max_subseq, tmp_subseq, key=len) - каждый раз происходит сравнение длин списков.

arr = [-5, 1, 2, -6, 2, 4, 5, -12, 2, 5, 6, 7]

max_subseq = []
tmp_subseq = []
for num in arr:
    tmp_subseq = tmp_subseq + [num] if num > 0 else []
    max_subseq = max(max_subseq, tmp_subseq, key=len)

print(max_subseq)

Output

[2, 5, 6, 7]

БЛОГ НА HUSL

Как найти положительную подпоследовательность наибольшей длины?

Ответы (4 шт):