动态规划|动态规划 — 最长上升子序列
**************************** 这是我第一次写博客啦啦啦啦啦啦 ****************************
最长上升子序列，我是在code up上面看到的，原题如下：
http://codeup.cn/problem.php?cid=100000627&pid=0
【动态规划|动态规划 — 最长上升子序列】题目描述：
一个数列ai如果满足条件a1 < a2 < … < aN，那么它是一个有序的上升数列。我们取数列(a1, a2, …, aN)的任一子序列(ai1, ai2, …, aiK)使得1 <= i1 < i2 < … < iK <= N。例如，数列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列，像(1, 7)， (3, 4, 8)和许多其他的子序列。在所有的子序列中，最长的上升子序列的长度是4，如(1, 3, 5, 8)。现在你要写一个程序，从给出的数列中找到它的最长上升子序列。
输入：
输入包含两行，第一行只有一个整数N（1 <= N <= 1000），表示数列的长度。第二行有N个自然数ai，0 <= ai <= 10000，两个数之间用空格隔开。
输出：
输出只有一行，包含一个整数，表示最长上升子序列的长度。
样例输入：
7
1 7 3 5 9 4 8
样例输出
4
直接放代码：
#include
#include
#include
using namespace std;
const int maxn = 1003;
int a[maxn], f[maxn];
int n,ans = 0;
int main()
{
scanf("%d", &n);
for(int i=1;
i<=n;
i++)
{
scanf("%d", &a[i]);
f[i] = 1;
//f(i)来表示前i个数以a[i]结尾的最长上升子序列长度。将所有初始值设为1
}
for(int i=1;
i<=n;
i++)
for(int j=1;
j 上述算法的时间复杂度为O（n^2），动态规划只是这道题的一种方法啦，还有很多其他方法，需要详解的可以看看这篇博客：https://blog.csdn.net/lxt_Lucia/article/details/81206439
推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术