结论： 任意一个 $n$ 个互异正整数的序列 $(a_1,a_2,a_3,\cdots,a_n)$，其最长递增子序列与最长递减子序列的长度之和不小于 $2\sqrt{n}$。（子序列不要求连续）

证明：

我们采用 DP 的思想，设 $f_i$ 为以 $a_i$ 结尾的最长递增子序列长度，$g_i$ 为以 $a_i$ 结尾的最长递减子序列长度。

对于正整数 $i<j$，若 $a_i<a_j$，则 $f_i<f_j$。若 $a_i>a_j$，则 $g_i>g_j$。

因此，每对 $(f_i,g_i)$ 互不相同，其中 $i=1,2,\cdots,n$。

设 $f_{i}$ 的最大值是 $k$，$g_i$ 的最大值是 $l$。

那么 $(f_i,g_i)$ 至多 $kl$ 对，至少 $n$ 对，因此 $kl\ge n$。

$k+l\ge2\sqrt{kl}\ge 2\sqrt{n}$，得证。

---

容易发现上述证明过程中的 $kl\ge n$ 很松，求加强上述证明或结论 /kel