既然是水杯套水杯，大小各不同，那么对于从里层往外层的水杯，它们的大小就形成了一个上升序列（按照题目的描述应该是不下降序列，但是数据范围中说明了水杯大小各不相同，所以其实是一个上升序列）。但是介于水杯的嵌套有两种方式：塞进里面和套在外面——也就是说对于这个上升序列，新的数既可能放在队头又可能放在队尾，因此这不是一道单纯的 LIS 问题。但是如果我们可以通过某种东洋魔术方法将这两种扩展序列的方式变为同一种，就可以将这个题变成一道 LIS 模版题。
虽然既有从前插入的数又有从后插入的数，但是我们可以发现这两种操作的特性：
- 从前插入与从后插入互不影响：从前插入需要保证最小，而从后插入的则应该是最大值——也就是说无论后面插入了什么数，对于前面的数插入时的大小判定都没有影响，反之亦然。
- 对于最开始的数，无论是接下来从前面插入的数还是从后面插入的数，在原序列中的位置都在这个数的后面。
第一个特性说明两种插入可以看作是整个问题的两个子问题，而第二个特性说明两个子问题又有联系，也许可以一口气解决。
为了描述方便我们姑且把答案序列中最先插入的那个数叫做「初始数」。在最终求得的单调上升序列中：从初始数往后一直到序列末尾构成了原序列中以初始数开头的上升子序列（注意这个上升子序列不一定是最长的）；从初始数往前一只到序列开头构成了原序列中以初始数开头的下降子序列（同样这个下降子序列也不一定是最长的）。所以我们的答案序列可以看作是选原序列中的一个数，找到以它开头的一个上升子序列和一个下降子序列，并把下降子序列沿开头对折到上升子序列的前面构成的。由于两个子序列都以同一个数开头且单调性不同，不会有重复的数出现。
对于一个原始序列 3 2 4 1，可以做如下变换：
其中3就是我们选出的开头，也就是初始数。
于是这个题就转化成了「最大化上升子序列与下降子序列的长度之和」我们可以将原序列复制，并反向插入原序列之前，这样就可以将原序列中要求的下降子序列变成新插入部分的上升子序列，整个问题也就转化成了 LIS 问题——求出来的最长上升子序列就是答案序列。对于刚才的例子，处理过的原序列是 1 4 2 3 3 2 4 1，最长上升子序列是 1 2 3 4。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
int a[maxn*2],n,f[maxn*2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[n+i]);
for(int i=1;i<=n;i++)
a[n+1-i]=a[n+i],f[n+1-i]=f[n+i]=1;
f[0]=0;
int ans=0;
for(int i=1;i<=n*2;i++){
for(int j=1;j<=i;j++)
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
提交这段传统的 LIS 代码，你可以发现最后的三个 TLE。因为这段代码复杂度为 $O(n^2)$，对于本题的数据范围来讲效率过低。我们需要一种 $O(nlogn)$ 的 LIS 算法。
这里提供的算法是基于暴力贪心的二分算法，具体实现是：
- 定义
f[i]为长度为 i 的上升子序列的最末元素（用数组下标表示长度适合二分），如果有多个长度为 i 的上升子序列则记录最小的最末元素。 - 定义答案为 len，枚举序列 a 中的每个元素，若有
a[i]>f[len]则f[++len]=a[i]。 - 否则，从
f[1]到f[len-1]中找到一个 j，满足f[j-1]<a[i]<f[j],则根据 f 的定义，我们需要更新长度为 j 的上升子序列的最末元素，即d[j]=a[i]。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
int a[maxn*2],n,f[maxn*2];
int main(){
scanf("%d",&n);
if(n==0){
printf("0");
return 0;
}
int len=1;
for(int i=1;i<=n;i++){
scanf("%d",&a[n+i]);
a[n+1-i]=a[n+i];
}
f[1]=a[1];
for(int i=2;i<=n*2;i++){
if(a[i]>f[len]) f[++len]=a[i];
else{
int pos=lower_bound(f+1,f+len+1,a[i])-f;
f[pos]=a[i];
}
}
printf("%d\n",len);
}