最长（上升、下降、不升、不降）子序列

以下模版全是n^2，方便理解差别细微

最长升/降/不升/不降子序列这四种类型，

都可以概括成一句话。就是对于这个被选出的子序列中的每一个元素，都大于/小于/不小于/不大于子序列中的前一个元素。

最长上升子序列模版：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1100];
int f[1100];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        f[i]=1;
        for(int j=1;j<i;++j)
            if(a[i]>a[j]&&f[j]+1>f[i])f[i]=f[j]+1;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

//最长下降子序列模版：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1100];
int f[1100];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        f[i]=1;
        for(int j=1;j<i;++j)
            if(a[i]<a[j]&&f[j]>f[i]-1)f[i]=f[j]+1;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

->->->->->->->->->->->最长下降子序列&&最长上升子序列不同在于：a[i]a[j] 一个是前面数比后面数大，一个是反之

//最长不升子序列：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1100];
int f[1100];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        f[i]=1;
        for(int j=1;j<i;++j)
            if(a[i]<=a[j]&&f[j]>f[i]-1)f[i]=f[j]+1;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

//最长不降子序列：
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[1100];
int f[1100];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)
    {
        f[i]=1;
        for(int j=1;j<i;++j)
            if(a[i]>=a[j]&&f[j]>f[i]-1)f[i]=f[j]+1;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
        ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

->->->->->->->->->->->最长不降子序列&&最长不升子序列不同在于：a[i]<=a[j] a[i]>=a[j] 不降即：前面一个数大于等于后面一个数，不升即：前面一个数小于等于后面一个数

先来说一下nlogn的求解思想，令f[i]代表长度为i的最长不下降子序列的长度的最后一位最小是多少。为什么要记录最小是多少那？因为我们想要这个序列最长，那么只有末尾最小才能有更多的数接到它的后面构成一个更长的序列。这时我们就能得到一个性质：f数组是递增的。证明：f[i]代表的是长度为i的最长不下降子序列的结尾最小的数，如果它后面来了一个比它大的数，那么这个数一定能构成至少长度为i+1的最长不下降子序列，所以在f数组里一定不会比它的位置靠前。

所以开一个变量len来记当前找到的最长不下降子序列有多长了，如果a[i]>=f[len]，那么直接放到f[len]后面,并且len++,但是如果a[i]<len,就要a[i]放到f数组里，这是我们用到二分，在f数组里找出大于a[i]的第一个数并且用i把它替换掉。原理：假设f[x]是大于a[i]的第一个数，那么x之前的所有数都不必a[i]大，那么把a[i]一定可以构成一个长度为x的最长不下降子序列，并且由于a[i]比f[x]更小，所以a[i]一定不会比f[x]不优。

有一个值得说明的点是f数组只是用来记录结尾的数的，f数组连起来并不是一个最长不下降子序列

最长上升子序列也是一样的道理，只不过由于要求严格递增，所以要替换的是大于等于它的第一个数

唔，二分用的2个stl分别是lower_bound和upper_bound，第一个是求大于等于一个数的第一个数的位置，第二个是求大于一个数的第一个数的位置。

//最长上升子序列nlogn算法 模版：
#include<algorithm>
#include<iostream>
#include<Cstdio>
using namespace std;
int n;
int a[100005],f[100005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    f[1]=a[1];int len=1;
    for(int i=2;i<=n;++i)
    {
        if(a[i]>f[len])f[++len]=a[i];
        else {
            int tmp=lower_bound(f+1,f+len+1,a[i])-f;
            f[tmp]=a[i];
        }
    }
    cout<<len;
    return 0;
}

//最长不下降子序列nlogn算法 模版：
#include<algorithm>
#include<iostream>
#include<Cstdio>
using namespace std;
int n;
int a[100005],f[100005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    f[1]=a[1];int len=1;
    for(int i=2;i<=n;++i)
    {
        if(a[i]>=f[len])f[++len]=a[i];
        else {
            int tmp=upper_bound(f+1,f+len+1,a[i])-f;
            f[tmp]=a[i];
        }
    }
    cout<<len;
    return 0;
}
//lower_bound()：找到大于等于某值的第一次出现 
//upper_bound()：找到大于某值的第一次出现 
//必须从小到大排序后才能用

closefrom

最长（上升、下降、不升、不降）子序列

都可以概括成一句话。就是对于这个被选出的子序列中的每一个元素，都大于/小于/不小于/不大于子序列中的前一个元素。

P1387 最大正方形