Lengths of increasing/decreasing subsequences of a finite sequence of real numbers 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 point out, we should be wary about trusting patterns for small values.
 A: The statement $m(n)=n$ is (also) true, because of the (very slightly stronger) fact:

If for a sequence of numbers the lengths of the longest weakly increasing and of the longest strictly decreasing sequence are respectively $pq$, then $n\leq pq$.

Two proofs. One is to assign to each term $x_i$ of the sequence a pair $(k,l)$ where $k$ is the length of the longest weakly increasing subsequence ending with $x_i$, and $l$ the length of the longest strictly decreasing subsequence ending with $x_i$. Then $1\leq k\leq p$ and $1\leq l\leq q$ and for $i<j$ the pair $(k',l')$ attached to $x_j$ has either $k'>k$ (if $x_i\leq x_j$) or $l'>l$ (otherwise), so in particular $(k',l')\neq(k,l)$ always. As there are only $pq$ possible pairs for $n$ terms, one must have $n\leq pq$. See this note by E. W. Dijkstra (second example) and also this answer by @Ross Millikan.
The other proof is to apply Schensted insertion to the sequence, which results in a pair of tableaux of a shape with $q$ rows and $p$ columns; since the shape (a Young diagram) fits inside the rectangle of those dimensions, one gets $n\leq pq$.
A: For $M(n)$ you are correct.  This follows from the AM-GM inequality.  You have two numbers that sum to $n$ and want to maximize the product.  This happens when you split it as evenly as possible.
