I have a simple idea, but I am not sure whether this is correct or not.

We can adopt a "hash table" to record the integers that have appeared in the set, i.e., for some integer N, if it appears in the set, then hash[N] = 1; otherwise hash[N] = 0. Then, the problem is equivalent to finding out the longest sub-sequence consisting of "1"s. If I were correct, this solution has complexity O(n). However, this approach fails if the maximum integer turns out to be too large, for instance, 10⁹.

On the one hand, using a hash table, we can dfs/bfs and find connected components on the path graph (add an edge for each adjacent elements) to solve the problem in Θ(n) expected time.

On the other hand, on the algebraic decision tree model, your problem cannot be solved in O(n) time. To see this, take an instance of the set disjointness problem (A, B) and transform it to [3A₁, ..., 3A_n, 3B₁ + 1, ..., 3B_n + 1]. Because the set disjointness problem has lower bound [1], your problem has the same bound.

• [1] Ben-Or, Michael. Lower bounds for algebraic computation trees.