Longest AP that can be formed (with difference 1) in an unsorted array of integers
If you're allowed to use hash tables, you can get a linear time algorithm.

Go over all nodes, putting the unique nodes in a hashtable, and constructing a new array only with the unique values. Now go over the new array and upgrade it to a graph $G = (V,E)$ in which $V$ are the unique values and the edges connect $i$ to $i+1$. Go over the graph, and whenever you see a vertex with no incoming edge, follow the unique path emanating from it and count its length. The answer is the maximal length of such a path.

This solution uses a hashtable to efficiently construct the graph. This suggests that you might not be able to do better than $n\log n$ if you are only allowed to use comparisons. One way to prove it would be by reduction from element uniqueness, which is known to require $n\log n$ comparisons.