f[i] 表示 以 a[i] 为结尾的上升子序列的最大值
a[i] 的前一项 的下标可能值 从 0 到 i-1
状态计算：if(a[i]>a[j]) f[i] = max(f[i],f[j]+1)

dp时间复杂度的分析方法 状态数*状态计算数 本题O(n^2)

C++ 代码

#include<iostream>

using namespace std;

const int N=1010;

int n;
int a[N];
int f[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)res=max(res,f[i]);

    cout<<res<<"\n";

    return 0;
}

还可以存储下找到的最长上升子序列。
在开一个数组，g[i] 记下以 a[i] 为结尾的最长上升子序列的 前一项 的下标

/*
最长上升子序列  记录状态转移，存下那个最长的子序列
*/
#include<iostream>
#include<cstring>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];
int g[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        g[i] = 0;
        for (int j = 1; j < i; j++)
        {
            if (a[i] > a[j])
            {
                if(f[i]<f[j]+1){
                    f[i] = f[j + 1] + 1;
                    g[i] = j;// g[i] 记下以 a[i] 为结尾的最长上升子序列的 前一项 的下标
                }  
            }
        }
    }

    int k = 1;
    for (int i = 1; i <= n; i++)
    {
        if(f[k]<f[i])
            k = i;
    }
    int len = f[k];
    cout << len << "\n";

    int res[1010];
    int cnt=len;
    //现在 k 存的是最长子序列 最后一个值 的下标
    for (int i = 0; i < len;i++){//最长上升子序列的倒序输出
        res[cnt--]=a[k];
       // cout << a[k] << " ";
        k = g[k];//k 从序列的倒数第一个 变为倒数第二个 第三个……
    }

    for(int i=1;i<=len;i++)cout<<res[i]<<" ";

    return 0;
}