AcWing 895.最长上升子序列

AcWing 895.最长上升序列

题目描述

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

输入格式

第一行包含整数N。

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

输出格式

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

数据范围

1≤N≤1000，
−109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

题解

一道动态规划的题目，利用数组存下来到这个点的最长上升子序列

思路

找到每一个值前面满足条件的最大的上升序列的值然后加上自己
每一个点的最长上升序列存在数组中

代码如下

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, a[N], dp[N];

int main(){
    cin.tie(0);
    cin >> n;

    for(int i = 0; i < n; ++i) cin >> a[i];

    dp[0] = 1;
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j)
            if(a[i] > a[j]) 
                dp[i] = max(dp[j] + 1, dp[i]);
        if(dp[i] == 0) dp[i] = 1;//如果dp[i] == 0,就是说明i前面的所有值都比它大
    }

    int ans = 0;
    for(int i = 0; i < n; ++i)
        ans = max(dp[i], ans);
    cout << ans << endl;

    return 0;
}