最长不下降子序列

上升子序列：元素各不相同

不下降子序列：元素可以相同

即   将上升子序列改一个if条件里面的即可

//最长不下降子序列
#include
#include
#include
#include
using namespace std;
const int N = 100010;
int a[N],f[N];
int n;
int main()
{
    int ans = 1;
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
       f[i] = 1;
    }
    for(int i = 2;i <= n;i++)
    {
        for(int j = 1;j <= i;j++)
        if(a[i] >= a[j])f[i] = max(f[i],f[j]+1);
        ans = max(ans,f[i]);
    }
    cout<
    return 0;
}

若用二分查找就要改两处

#include
#include
#include
using namespace std;
const int N = 2020;
int a[N],f[N];//f[]记录上升子序列
int len;//上升子序列的长度
int find(int x)//二分查找第一个大于x的位置 
{
    int l = 1,r = len,mid;
    while(l <= r)
    {
        mid = (l+r)>>1;
        if(x >= f[mid]) l = mid+1;
        else r = mid-1;
    }
    return l;
}
//也不是不可以用lower_bound( )
int main()
{
    cin>>n;
    len = 1;
    for(int i = 1;i <= n;i++)cin>>a[i];
    f[1] = a[1];//把第一个元素添加进f[ ]中
    
    //考虑新加进来的a[i]
    for(int i = 2;i <= n;i++)
    {
        //大于则添加
        if(a[i] >= f[len])f[++len] = a[i];
    
    else//小于等于则替换 
    {
        int j = find(a[i]);
        f[j] = a[i];
    }
    }
    cout<
 
    return 0;
}
 

若我们要输出不下降子序列里的最长上升子序列怎么办呢？

那我们这时候就需要用一个pre[ ]数组来记录原数组a[ ] 的下标(ps:这里是前一个元素下标)

二分查找的优点：求解长度快

缺点：不能输出子序列！！！

所以这里我们需要用第一种方法即可

#include
#include
#include
using namespace std;
const int N = 1020;
int a[N],f[N],pre[N];
int longlen;
int n;
void print(int i)
{
    if(pre[i]) print(pre[i]);
    printf("%d ",a[i]);
}
int main()
{
    int ans = 1;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)f[i] = 1;
 
    for(int i = 2;i <= n;i++)
    {
        for(int j = 1;j < i;j++)
        if(a[i] > a[j] && f[i] < f[j] + 1)
        {
            f[i] = f[j] + 1;
            pre[i] = j;//记录前驱
        }
        if(f[i] > ans)
        {
            ans = f[i];
            longlen = i;
        }
    }
    printf("%d\n",ans);
    print(longlen);
    return 0;
}