Мой код решает задачу, но не вписывается по времени, вроде работает за n logn как и должен. Возможно что-то упустил в бинарном поиске или в условиях после выхода из него. Сейчас думаю, что просадка идет при одинаковых элементах, т.е. я храню и [5,4] и [5,4,4], хотя первый уже не нужен и он тормозит поиск, можно его удалять, но это, наверно, долго, возможно заменять None, но пока не придумал как.
from array import array
def b_search3(xs, q):
l, h = 0, len(xs)-1
while l < h:
mid = (l + h+1)//2
if q > xs[mid]:
h = mid -1
else:
l = mid
return h
def max_sequence(l):
temp = list()
temp.append(array('i', (l[0],)))
for i, v in enumerate(l[1:]):
current = b_search3(tuple(x[-1] for x in temp), v)
if v > temp[current][-1]:
temp[current][-1] = v
else:
new = temp[current] + array('i', (v,))
if len(new) > len(temp):
temp.append(new)
elif v > temp[len(new)-1][-1]:
temp[len(new)-1] = new
answer = []
prev = 0
for el in temp[-1]:
prev += l[prev:].index(el) +1
answer.append(str(prev))
return '\n'.join((str(len(temp[-1])), ' '.join(answer)))
def main():
import sys
reader = (map(int, line.split()) for line in sys.stdin)
next(reader)
l = array('i')
l.fromlist(list(next(reader)))
print(max_sequence(l))
if __name__ == '__main__':
main()
Условие:
Дано целое число 1≤n≤10^5 и массив A[1…n]A[1…n], содержащий неотрицательные целые числа, не превосходящие 10^9. Найдите наибольшую невозрастающую подпоследовательность в A. В первой строке выведите её длину k, во второй — её индексы 1≤i1
