本题要求：
有一个长为n的数列
a0
…。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i < j都满足
ai
<
aj
的子序列
输入格式：
第一行输入n 接下来n行输入ai
输出格式：
输出长度
输入样例：
5 4 2 3 1 5
输出样例：
3
解题思路 :
用dp来存储从0到ai中上升序列的最长长度，下标表示ai
代码 :
#include <iostream>
#include <cstring>
using namespace std;
int dp[
1001];
int main() {
int n;
cin >> n;
int a[
101];
for (
int i =
0; i < n; i++) {
cin >> a[i];
}
int res =
0;
for (
int i =
0 ; i < n; i++) {
dp[i] =
1;
for (
int j =
0; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] +
1);
}
}
res = max(res, dp[i]);
}
cout << res << endl;
return 0;
}
