题目描述

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−109≤数列中的数≤109

样例

输入样例:
7
3 1 2 1 8 5 6

输出样例：
4

算法1

(暴力枚举) $O(n^2)$

• 状态表示 dp[i]
  • 集合： 所有以第i个数字结尾的上升子序列的集合
  • 属性： 集合中的子序列长度的最大值
• 状态计算
  • 枚举上升子序列的倒数第二数，不妨以坐标j表示，若 a[j] < a[i] 则 dp[i] =max(dp[i], dp[j] + 1)
• 备注
  • 需要注意的是dp的长度取法不同， 对应的a[j] a[i]的坐标细节不同

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int N;
    cin >> N;

    int a[N];
    for(int i = 0; i < N; i++)scanf("%d ", &a[i]);

    int dp[N + 1] ;              // 因为用的值 之前会计算出来，所以可以不用 `int dp[N+1] = {0};
    int res = 0;

    for(int i = 1; i <= N; i++)   // i从1 开始 所以 <= N 
    {
        dp[i] = 1;
        for(int j = 1; j < i; j++)
        {
            if(a[j - 1] < a[i - 1]) 
                dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res ,dp[i]);
    }

    cout << res << endl;

    return 0;
}