Approximating longest path on graphs with average degree n/2
Here is something to get you started.
Suppose that your graph were $n/2$-regular, and consider the following algorithm. Start at an arbitrary vertex $v_1$. Choose one of its $n/2$ neighbors $v_2$. Choose one of $v_2$'s $n/2$ neighbors $v_3 \neq v_1$. And so on. The process will continue for at least $n/2+1$ steps. Since every path has length at most $n$, this gives a $1/2$ approximation. In fact, this would work even if the minimal degree were at least $n/2$.