Upd: I got a few things mixed up, now fixed.

Recently, I meet some problems that promised the data input is random, so there may be some interesting properties to solve the problem.

Given a sequence of length $$$n$$$, every number in it have a random value in $$$[1,n]$$$.

The expected value of the length of longest increasing subsequence is $$$\sqrt n $$$.

The expected value of the biggest of prefix sum is $$$\frac{n*(n+1)}{2}$$$.

Given a sequence of length $$$n$$$, every number in it have a random value $$$1$$$ or $$$-1$$$.

The expected value of the biggest of prefix sum is $$$\sqrt n$$$.

But I can't prove it.

Can anyone prove it, or does anyone know more about the properties of random numbers?

Leave a comment if you know, thanks.