学步园

非常经典的问题，拿来给大家练手了。 

序列 { 1,2,...,n } 的一个子序列是指序列 { i1, i2, ……, ik },其中 1<=i1 < i2 < …… < ik<=n, 序列 { a1, a2, ……, an } 的一个子序列是指序列 { ai1, ai2, ……, aik },其中 { i1, i2, ……, ik } 是 { 1, 2, ……, n } 的一个子序列.同时,称 k 为此子序列的长度. 

如果 { ai1, ai2, ……, aik } 满足 ai1 ≤ ai2 ≤ …… ≤ aik,则称之为上升子序列.如果不等号都是严格成立的,则称之为严格上升子序列.同理,如果前面不等关系全部取相反方向,则称之为下降子序列和严格下降子序列. 

长度最长的上升子序列称为最长上升子序列.本问题对于给定的整数序列,请求出其最长严格上升子序列的长度

第一行，一个整数N。

第二行 ，N个整数（N < = 5000）

输出K的极大值，即最长严格上升子序列的长度

5

9 3 6 2 7

3

【样例解释】

最长严格上升子序列为3,6,7

【说明】

此题非常基础，希望每个人都能拿到此题的全部分数

题解：

#include <iostream>
using namespace std;
int dp[5555] = {0};
int n;
int a[5555];
int k = 0;
int maxV = 0;

int main()
{
	cin >> n;
    for(int i=1; i<=n; i++) cin>>a[i];
    dp[1] = 1;
    for(int i=2; i<=n; i++)
    {
      maxV = 0;
      for(int j=1; j<i; j++)
      {
        if(maxV<dp[j] && a[j]<a[i]) maxV = dp[j];
      }
      dp[i] = maxV + 1;
      if(k<dp[i]) k = dp[i];
    }
    cout << k;
	return 0;
}