Как найти наибольшую поседовательность за O(n)?
банальным проходом с подсчетом длины текущей последовательности
Хранить hash map, в которой ключ - значение последнего элемента в последовательности встреченной раньше, а значение -- длина. И дальше проходим по массиву и заполняем.