Вопрос Лёгкая Наибольшая возрастающая подпоcледовательность.

[Vetal]

Ограничение по времени работы программы: 2 секунды







Дана последовательность целых чисел. Постройте наибольшую возрастающую подпоследовательность данной последовательности.





Входные данные





В первой строке входных данных записано число элементов последовательности N,0 < N < 1001 . Во второй строке записаны N целых чисел через пробел.







Выходные данные





Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности (последовательность чисел через пробел). Если таких подпоследовательностей несколько, необходимо вывести одну (любую) из них.







у меня вот такой код, но проходит только на 4 теста из 18

 

[xGorecx]

N до тысячи... Тут даже квадрат зайдет. Банальная динамика:
d - длина НВП, оканчивающейся в i-том элементе
изначально все d'шки равны 1 (последовательность из 1 элемента не нарушает условий)
дальше простецкие переходы: перебираем каждый элемент(i) и вложенным циклом все элементы до текущего(j). Если a > a[j], то d = max(d, d[j] + 1).
Ну и в конце, думаю, уже и сам догадался, что берем максимум из всех d'шек, это длина НВП.

Ответ восстанавливаешь рекурсивно: запоминаешь индекс наибольшей d'шки и идешь от него назад пока не встретишь индекс с d'шкой равной длине НВП минус один и a'шка, которого меньше, чем a'шка последнего элемента, и так далее.

Я питонист, конечно, так себе, но вот, что на скорую руку набросал:

Теперь советую подумать как оптимизировать до O(nlogn)

 

[constantine]

Что значит "наибольшая"? Самая длинная? Содержащая самый большой элемент? Содержащая самую большую сумму элементов?

Как получаем подпоследовательность? Просто берём срез? Или можно выбрасывать отдельные элементы?

Если правильны первые варианты, то: _, a = input(), list(map(int, input().split()))
a += [a[-1] - 1] # заглушка - чтобы не городить лишние проверки
max_start, max_len, cur_start, cur_len = 0, 0, 0, 1
for i in range(1, len(a)):
if a > a[i - 1]: cur_len += 1
else:
if cur_len > max_len: max_start, max_len = cur_start, cur_len
cur_start, cur_len = i, 1
print(*a[max_start : max_start + max_len])

 

[M1racle]

Если можно выбрасывать элементы, то какая же это подпоследовательность ? Это уже не подпоследовательность, а чёрти что! В любой возрастающей (но не строго возрастающей !) подпоследовательности каждый последующий элемент (если он есть) не может быть меньше предыдущего. Одно из самых простых (но отнюдь не оптимальных !) решений здесь такое:

Но наверняка можно придумать и что-то более хитрое. А если подпоследовательность максимальной длины должна быть всё таки не возрастающей, а строго возрастающей, то это несколько иная задача. Также как и задача с "подпоследовательностью", которая таковой вообще не является...

 

[Максим21]

чел выше по фактам раскидал )

 

[1stLeader]

>>>