题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3530
题目大意：找到一个最大的子串,使得子串区间内最大值和最小值的差在L和R范围内。
Sample Input
5 0 0 1 1 1 1 1 5 0 3 1 2 3 4 5
Sample Output
5 4
emmm，真的，看到subsequence ，这不是子序列嘛。。。既然是无序的，那么我们sort一下不就完事了嘛。。。。结果，题目没有描述清楚。。。实际上是子串。。。
那么我们维护一下最大值和最小值就好了，本来RMQ也是可以做的。。。只不过会T。。所以只能想$O(n)$的做法了，那么很明显就是单调队列了。我们用一个队列来维护当前的最大值，一个来维护当前的最小值，这个很好办：
while (head1<=tail1 && a[q1[tail1]]>a[i]) tail1--; q1[++tail1]=i; while (head2<=tail2 && a[q2[tail2]]<a[i]) tail2--; q2[++tail2]=i;
接下来我们剔除掉差距过大的，差距太小不能剔除掉，因为后面可能还有大的，就会拉大差距，剔除过程如下：
while (a[q2[head2]]-a[q1[head1]]>R) { if (q1[head1]<q2[head2]) st=q1[head1++]; else st=q2[head2++]; }
需要值得注意的是，st得出来的是最后一个不合法的，要找到最小合法的id，那么可以将st+1,但没必要，因为后面计算长度的时候还要头减尾+1，所以我们可以直接将st当做尾巴，这样就省得多写几个+1了
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int mac=1e5+10; int a[mac],q1[mac],q2[mac];//上升序列，下降序列 int main(int argc, char const *argv[]) { int n,L,R; while (~scanf ("%d%d%d",&n,&L,&R)){ for (int i=1; i<=n; i++) scanf ("%d",&a[i]); int head1=1,tail1=0,head2=1,tail2=0; int ans=0,st=0; for (int i=1; i<=n; i++){//从i开始最多能够往前拓展的最大长度 while (head1<=tail1 && a[q1[tail1]]>a[i]) tail1--; q1[++tail1]=i; while (head2<=tail2 && a[q2[tail2]]<a[i]) tail2--; q2[++tail2]=i; while (a[q2[head2]]-a[q1[head1]]>R){ if (q1[head1]<q2[head2]) st=q1[head1++]; else st=q2[head2++]; } if (a[q2[head2]]-a[q1[head1]]>=L && a[q2[head2]]-a[q1[head1]]<=R) ans=max(ans,i-st); } printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/lonely-wind-/p/13266333.html