描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 ii 和 jj 满足 i<ji<j 且 arr_i \geq arr_jarri≥arrj。
数据范围： 0\leq n \leq 10000≤n≤1000 , |arr_i| \le 10^9 \∣arri∣≤109 
要求：时间复杂度 O(n^2)O(n2)， 空间复杂度 O(n)O(n)

输入描述：

第一行输入一个正整数 n ，表示数组的长度 
第二行输入 n 个整数表示数组的每个元素。

输出描述：

输出最长严格上升子序列的长度

示例1

输入： 
7
6 3 1 5 2 3 7
复制
输出： 
4
复制
说明： 
该数组最长上升子序列为 [1,2,3,7] ，长度为4
解题思路：
1、定义dp[i]为以in[i]为结尾时的最长上升子序列的长度；
2、此时做选择，in[i]只能放入最长上升子序列，且in[i]放入后，其长度等于前i-1的上升子序列最大值+1
即in[i]>in[0...i-1]时
dp[i]=max(dp[0...i-1])+1;
in[i]<in[0...i-1]时
加入in[i]后的最长上升子序列只有其本身，故dp[i]=1；

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> in(n+1, 0);
        for (int i = 0; i < n; i++) {
            cin >> in[i+1];
        }
        vector<int> dp(n+1, 0); // dp[i]代表以in[i]做结尾时对于的最长上升子序列长度
        
        for (int i = 1; i <= n; i++) {
            int cnt = 0;
            for (int j = 0; j < i; j++) {
                if (in[i] > in[j]) {
                    cnt = max(cnt, dp[j]);
                }
            }
            dp[i] = cnt + 1;
        }
        sort(dp.begin(), dp.end());
        cout << dp[n] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")