最长递减子序列（不一定连续）：DP

思路：统计以s[i]结尾的递减子序列的最大长度dp[i]

分为2类：是否比前面所有元素都大

  • ①是 前面序列对其没有贡献:lenth[i]=1
  • ②否 前面序列对其有贡献:dp[i]=max(dp[j]+1 )（需遍历s[i]前面所有元素，保留最大值）
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=26;
int s[maxn];//输入
int dp[maxn];//以s[i]结尾的递减子序列的最大长度dp[i]

int missile(int n){
    fill(dp,dp+n,1);
    int sum=0;
    for(int i=0;i<n;i++){
        if(i==0)dp[i]=1;
        for(int j=0;j<i;j++){
            if(s[j]>=s[i])dp[i]=max(dp[i],dp[j]+1);
        }
        sum=max(sum,dp[i]);
    }
    return sum;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        printf("%d\n",missile(n));
    }
    return 0;
}

优化：根据递减子序列长度i，记录子序列中的最小值support[i]（若有相同子序列，取较大的最小值）

便于二分查找

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=26;
int s[maxn];
int support[maxn];

int binaryfind(int lenth,int x){//二分查找第一个小于x的位置
    int left=0;
    int right=lenth;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(support[mid]<x)right=mid-1;
        else left=mid+1;
    }
    return left;
}

int missile(int n){
    int lenth=0;
    support[lenth]=0x7fffffff;
    for(int i=0;i<n;i++){
        if(s[i]<=support[lenth])support[++lenth]=s[i];
        else {
            int pos=binaryfind(lenth,s[i]);//找到第一个小于s[i]的数的对应位置
            support[pos]=s[i];//更新此长度的对应的最小值(较大的)
        }
    }
    return lenth;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        printf("%d\n",missile(n));
    }
    return 0;
}