Let $x\_1,\ldots,x\_n$ be a finite sequence of real numbers. Let $f(\{x\_i\}\_{i=1}^n)=f(\{x\_i\})$ be the length of the largest non-decreasing subsequence, and let $g(\{x\_i\})$ be the length of the largest non-increasing subsequence.

Define the function

$$m(n)=\min\_{\{x\_i\}}f(\{x\_i\})g(\{x\_i\})$$

Considering a strictly increasing sequence, we can see that $m(n)\le n$. Is it true that $m(n)=n$ for all $n\in\mathbb{N}$?

Similarly, define $f'$ ($g'$) as the length of the largest *strictly* increasing (decreasing) subsequence, and define

$$M(n)=\max\_{\{x\_i\}}f'(\{x\_i\})g'(\{x\_i\})$$

Considering a 'mountain', that is, a sequence that strictly increases through its first half, and then strictly decreases through its second half, we see that 
$$M(n)\ge \begin{cases}\frac{n(n+2)}{4}&n\text{ even}\\\frac{(n+1)^2}{4}&n\text{ odd}\end{cases}$$

Is this actually an equality for all $n\in\mathbb{N}$? This all checks out for small values of $n$, but as the answers to [this question](https://math.stackexchange.com/questions/111440/examples-of-apparent-patterns-that-eventually-fail) point out, we should be wary about trusting patterns for small values.