题解 | #Redraiment的走法#

#include <stdio.h>

int main()
{
    int n;
    scanf("%d",&n);
    int a[n],i,j;
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    
    int dp[n]; //从下标为n走最多有dp[n]种走法
    for(i=0;i<n;i++) dp[i]=1;//初始化赋值为1，算自身的一步
    
    for(i=n-2;i>=0;i--)//从后向前遍历
        for(j=i+1;j<n;j++)
            if(a[i]<a[j])
                if(dp[i]<1+dp[j]) dp[i]=1+dp[j];
    
    int max=0;
    for(i=0;i<n;i++)
        if(max<dp[i]) max=dp[i];
    printf("%d",max);
    return 0;
}