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


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


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.

  • $\begingroup$ I don't understand.. Isn't $M(n) = 1,\,\forall n$? Consider the sequence $\pi,\pi,\pi,\pi,...$? $\endgroup$ – Lord Soth Apr 12 '13 at 23:57
  • $\begingroup$ Oh the second one is a maximization, OK. $\endgroup$ – Lord Soth Apr 12 '13 at 23:59

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$.

  • $\begingroup$ Wonderful. Thank you! $\endgroup$ – Jared Apr 15 '13 at 17:13

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.

  • $\begingroup$ Sure. This is clear. Thank you. Any ideas for $m(n)$? $\endgroup$ – Jared Apr 13 '13 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.