(dp) $O(n^2)$

对于序列中两个相同的数 $a[i] .... a[j],a[i]=a[j]$，且i~j之间的数都大于等于$a[i]$,那么$g[i]=g[j]$，此时g[i]可以和前i个数构成的lcs，也完全包括在a[j]和前j个数组成的lcs中，所以此时需要将a[j]构成的多余部分删除。

C++ 代码

#include <iostream>
#include <set>
using namespace std;
const int N=5100;
int g[N],a[N],n;
typedef long long LL;
LL ans,f[N];
int main(){
    int m=1;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i){
        g[i]=1;
        for(int j=1;j<i;++j){
            if(a[j]>a[i]) g[i]=max(g[i],g[j]+1);
        }
        m=max(m,g[i]);
    }
    for(int i=1;i<=n;++i){
        if(g[i]==1) f[i]=1;
        for(int j=1;j<i;++j){
            if(a[j]>a[i]&&g[i]==g[j]+1) f[i]+=f[j];
            else if(a[j]==a[i]&&g[i]==g[j]) f[i]=0;
        }
    }
    LL ans=0;
    for(int i=1;i<=n;++i) 
        if(g[i]==m) ans+=f[i];
    cout<<m<<' '<<ans<<endl;
    return 0;
}