题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。（允许不相邻）

样例

输入样例

7
3 1 2 1 8 5 6

输出样例

4

好了，来康康这道题。
这道题很明显是动态规划问题（显然DFS过不了），毕竟题目标签也非常直白的告诉了我们

那我们应该这么做呢？
调用模板

算法1

(动态规划) $O(n^2)$

时间复杂度

两重循环，时间复杂度为$O(n^2)$。

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N]; //输入用的数组
int f[N]; //用来存储每个答案，在最后要for循环遍历找最大值（被坑了）
int main(){
    int n; //字符个数
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++){
        f[i] = 1; //付初值。即使这个数后面没有比它大的数，它本身也算一个
        for(int j = 1;j <= i;j ++){
            if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1); //如果这个数大于前面那个数，说明是合法的，把它等于max(f[i],f[j] + 1)
        }
    }
    int res = -1; //最长上升子序列的答案，因为a数组中的数字有可能为负数，所以要付成很小的数
    for(int i = 1;i <= n;i ++) res = max(res,f[i]); //找最大值~
    printf("%d\n",res); //输出最后答案~
    return 0;
}

附：动态规划优化版

先讲讲优化思路，我们发现在计算f时，i循环已经把f数组遍历了一遍，于是，我们可以优化掉最后找最大值的那重循环（虽然也没优化多少）

参考文献

C++代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N]; //输入用的数组
int f[N]; //用来存储每个答案，在最后要for循环遍历找最大值（被坑了）
int main(){
    int n; //字符个数
    int res = -1; //最长上升子序列的答案
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++){ //在这已经遍历了f数组
        f[i] = 1; //付初值。即使这个数后面没有比它大的数，它本身也算一个
        for(int j = 1;j <= i;j ++){
            if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1); //如果这个数大于前面那个数，说明是合法的，把它等于max(f[i],f[j] + 1)
        }
        res = max(res,f[i]); //就是这啦，因为i从1到n已经遍历了f数组，在这下面找最大值是没问题的~
    }
    printf("%d\n",res); //输出最后答案~
    return 0;
}

算法2

(递归) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int a[N],f[N];
int n;
int dfs(int x){
    if(f[x]) return f[x]; //如果被算过了，返回
    int ans = 0;
    //计算
    if(x != 1){
        for(int i = x - 1;i >= 1;i --){
            if(a[x] > a[i]) ans = max(ans,dfs(i)); //如果大于，那么说明是合法的，把ans赋为大的那个数
        }
    }
    f[x] = ans + 1; //在算上本身~
    return f[x]; //返回答案
}
int main(){
    scanf("%d",&n); //输入字符个数
    for(int i = 1;i <= n;i ++){
        scanf("%d",&a[i]); //把数组输入
    }
    int res = -0x3f3f3f3f; //一定要赋为很小的数哦，不然会过不了
    for(int i = 1;i <= n;i ++) res = max(res,dfs(i)); //找最大数
    printf("%d\n",res); //输出答案
    return 0;
}