给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−10^9≤数列中的数≤10^9
输入样例：
1. 7 2. 3 1 2 1 8 5 6
输出样例：
4
思路：弄清楚状态划分就行，dp[i]表示i下表下的最长升序长度，以此状态转移方程就是dp[i]=max(dp[j]+1) j=1,2,3,4.....n-1.
带注释代码：
#include <iostream> using namespace std; #include <algorithm> const int N = 1010; int a[N]; // 存储输入的序列 int dp[N]; // dp数组用于记录以第i个元素结尾的最长递增子序列的长度 int main() { int n; cin >> n; // 输入序列的长度 // 读取输入序列 for (int i = 1; i <= n; i++) cin >> a[i]; // 动态规划求解最长递增子序列长度 for (int i = 1; i <= n; ++i) { dp[i] = 1; // 初始值，每个元素自成一个长度为1的递增子序列 for (int j = 1; j <= i; ++j) { if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]为当前最大长度 } } int res = 0; // 用于存储最终结果，即最长递增子序列的长度 // 找到dp数组中的最大值，即为最长递增子序列的长度 for (int i = 1; i <= n; i++) res = max(res, dp[i]); // 输出结果 cout << res << endl; return 0; }
