  The longest increasing subsequence of a random walk with mean zero and finite
variance is known to be $n^{1/2 + o(1)}$. We show that this is not universal
for symmetric random walks. In particular, the symmetric Ultra-fat tailed
random walk has a longest increasing subsequence that is asymptotically at
least $n^{0.690}$ and at most $n^{0.815}$. An exponent strictly greater than
$1/2$ is also shown for the symmetric stable-$\alpha$ distribution when
$\alpha$ is sufficiently small.
