Задача которая встречалась на разных собеседованиях.

Дается массив чисел a1, a2, …., an. Найти максимальную по длине подпоследовательность, которые образует непрерывный набор чисел.
Например вам дали массив
10, 2, 4, 7, 5, 8, 3
Ответом будет 4 так как вы можете взять числа 2, 3, 4, 5

Решение:
Конечно вы можете отсортировать массив и за О(n) выделить максимальную по длине отрезок в котором числа идут друг за другом, но такой алгоритм требует O(n*logn) времени. Собеседующий вас попросит решение за О(n).
Чтобы решить задачу за О(n) давайте заведем словарь has, где has[x]=1 если число х встречается в массиве. После пройдемся слева направо по массиву, пусть вы сейчас зафиксировали число x, теперь вы хотели бы знать максимальное число r, что x+1, x+2, ….., r встречаются в словаре, а также минимальное число l, что в словаре встречаются числа x-1, x-2, …..,l.
Чтобы найти такие l, r вы можете в цикле пройтись увеличивая/уменьшая указатели пока числа встречаются в словаре. Таким образом вы нашли l, r и пытаетесь обновить ответ, но такое решение пока О(n^2), чтобы работало за линию вы должны создать словарь used в котором будете отмечать те числа которые вы посетили в словаре has, чтобы не пытаться искать l, r для уже посещенного х.
Время работы алгоритма О(n).

Псевдокод в комментариях.