AcWing 895.最长上升子序列Ⅰ

题目链接：http://www.acwing.com/problem/content/897/

浅浅复习

放AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 int n;
 6 int a[N], dp[N];//a[i]存储序列，dp[i]存储从第一个数到a[i]的最大公共子序列长度
 7 
 8 int main()
 9 {
10     cin >> n;
11     for(int i = 1; i <= n; i ++)
12         cin >> a[i];
13 
14     for(int i = 1; i <= n; i ++)
15     {
16         dp[i] = 1;
17         for(int j = 1; j < i; j ++)
18         {
19             if(a[j] < a[i])
20                 //前一个数的最大公共子序列长度加上自己
21                 dp[i] = max(dp[i], dp[j] + 1);
22         }
23     }
24 
25     int res = 1;
26     for(int i = 1; i <= n; i ++)
27         res = max(res, dp[i]);
28 
29     cout << res <<endl;
30     return 0;
31 }