最长非减字串3 (最长公共子串) 银牌

//最长递增（非减少）子序列

//最长公共子序列法

#include<bits/stdc++.h>

using namespace std;

const int MN=100;

int d[MN][MN];

vector<int> a,b;

int lcs(int m,int n){

    if(m<0 || n<0){//序列列举完了，递归退出

        return 0;

    }

    if(d[m][n]>0){//恢复记忆

        return d[m][n];

    }

    if(a[m]==b[n]){

        d[m][n]=lcs(m-1,n-1)+1;

    }else{

        d[m][n]=max(lcs(m-1,n),lcs(m,n-1));

    }

    return d[m][n];

}

int main(){

    int n;

    cin>>n;

    for(int i=0;i<n;i++){

        int tmp;

        cin>>tmp;

        a.push_back(tmp);

        b.push_back(tmp);

    }

    sort(b.begin(),b.end());

    cout<<lcs(a.size()-1,b.size()-1)<<endl;//从0到size-1

    return 0;

}