What do you mean by the expected value of the biggest prefix sum? If all integers are positive, then the biggest prefix sum is the sum of the whole values in the array. By linearity of expectation, this is $$$\frac{n(n + 1)}{2}$$$. Please tell where I'm going wrong :P

Let $$$U_n$$$ be the universal set of all possible $$$n$$$-element arrays $$$A_n = [a_1 a_2 \cdots a_n]$$$, where $$$1 \le a_i \le n$$$. The expected value for a function $$$f_n(A_n)$$$ should be computed as follows.

$$$E[f_n] = \sum\limits_{A_n\in U_n} f_n(A_n)/|U_n|$$$

where $$$|U_n| = n^n$$$ is cardinality of the universal set.

Let $$$g_n(A_n)$$$ and $$$h_n(A_n)$$$ be the length of the longest increasing subsequence of $$$A_n$$$ and the biggest prefix sum of $$$A_n$$$, respectively. It is simple to show that the range of $$$g_n(A_n)$$$ is $$$[1,n]$$$ while the range of $$$h_n(A_n)$$$ is $$$[n,n^2]$$$.

The expected value for $$$g_n$$$ and $$$h_n$$$ can then be rewritten as follows.

$$$E[g_n] = \sum\limits_{k=1}^{k=n} k \times g\_count(k,n)/|U_n|$$$

$$$E[h_n] = \sum\limits_{s=n}^{s=n^2} s \times h\_count(s,n)/|U_n|$$$

where $$$g\_count(k,n)$$$ is the number of $$$n$$$-element arrays $$$A_n$$$ whose length of the longest increasing subsequence is equal to $$$k$$$, and $$$h\_count(s,n)$$$ is the number of $$$n$$$-element arrays $$$A_n$$$ whose sum is equal to $$$s$$$.

$$$h\_count(s,n)$$$ is much simpler to compute using combinatorics analysis as follows.

$$$h\_count(s,n) = \binom{s-1}{n-1}$$$

I hope that these hints are helpful.

For the LIS problem, I think this article might help, but it's not easy to understand :(

For the first prefix sum problem, the expected value of one number is $$$\frac{1+n}{2}$$$, and all numbers are greater than 0, so the expected value of biggest prefix sum = the expected value of the sum of the sequence = $$$\frac{n\cdot(n+1)}{2}$$$.