Python

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

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



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


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


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



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


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



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

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

Я питонист, конечно, так себе, но вот, что на скорую руку набросал:
Теперь советую подумать как оптимизировать до O(nlogn) :)
Сергей Смольяков
Сергей Смольяков
12 614
Лучший ответ
Что значит "наибольшая"? Самая длинная? Содержащая самый большой элемент? Содержащая самую большую сумму элементов?

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

Если правильны первые варианты, то:
 _, 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[i] > 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])
ВЗ
Владимир Зверев
50 583
Нодир Ибрагимов Наибольшая, значит самая длинная в порядке возрастания
Нодир Ибрагимов можно выбрасывать элементы
Нодир Ибрагимов извините пожалуйста я забыл добавить ввод и вывод
ввод
3 29 5 5 28 6
вывод
3 5 28
Нодир Ибрагимов пожалуйста, если у вас есть время исправьте код или скажите как исправить
>>>
ВП
Владислав Проданюк
76 801
Нодир Ибрагимов извините пожалуйста забыл добавить ввод и вывод
ввод

3 29 5 5 28 6

вывод

3 5 28
Если можно выбрасывать элементы, то какая же это подпоследовательность ? Это уже не подпоследовательность, а чёрти что! В любой возрастающей (но не строго возрастающей !) подпоследовательности каждый последующий элемент (если он есть) не может быть меньше предыдущего. Одно из самых простых (но отнюдь не оптимальных !) решений здесь такое:Но наверняка можно придумать и что-то более хитрое. А если подпоследовательность максимальной длины должна быть всё таки не возрастающей, а строго возрастающей, то это несколько иная задача. Также как и задача с "подпоследовательностью", которая таковой вообще не является...
Карен Казарян
Карен Казарян
66 572
*¤Роман¤* Ачкасов с определением подпоследовательности тут все ок)
последовательность элементов, полученная удалением 0+ элементов из данной = подпоследовательность
последовательность элементов, взятая на непрерывном промежутке данной = подотрезок
Карен Казарян Сортировка по возрастанию действительно невозможна в строгом смысле, если в сортируемой последовательности находится хотя бы пара одинаковых элементов. Поэтому возрастание в основном и понимается в нестрогом смысле, как, кстати, наверное и в этой задаче.
А вот и правильное решение:Если же возрастание иметь в виду в строгом смысле, тогда из строки
A[j] >= maxi
просто надо убрать знак равенства...
чел выше по фактам раскидал )
AS
Aidos Seiitzhan
375

Похожие вопросы