最长上升子序列

#include <iostream>
using namespace std;

const int NN = 1010;
int N;
int dp[NN], num[NN];

int main(){
    cin >> N;
    // 这里把所有dp初始化为1，其实就是已经考虑了子序列只有倒数最后一个字符的情况，所以后面就只用考虑子序列中倒数第二个字符是1 ~ i - 1中的哪个就行了
    for (int i = 1; i <= N; i ++) {cin >> num[i]; dp[i] =  1;}
    for (int i = 2; i <= N; i ++){
        for (int j = i - 1; j >= 1; j --){
            if (num[j] < num[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    // cout << dp[N];  // 最长上升子序列不一定是是以最后一个数字结尾的
    int res = 0;
    for (int i = 1; i <= N; i ++) res = max(res, dp[i]);

    return 0;
}