3808最长不下降子序列(list)

3808   最长不下降子序列(list)

题目描述

给定长度为 N 的正整数序列 x1 ,x2 ,…,xn 。寻找它的一个最长子序列,使得子序列是不下降的,输出此子序列的长度。

输入格式:

共两行;
第一行输入一个整数n;
第二行输入n个整数;

输出格式:

输出一行;
寻找它的一个最长子序列,使得子序列是不下降的,输出此子序列的长度。
输入样例 复制
8
1 3 1 5 9 7 4 8
输出样例 复制
5

说明

定义 f [i] 表示在取第 i 个数时,前 i 个数的最长不下降子序列的最大长度,状态转移方程为:

f[i] = max{ f[j] } + 1(j

边界条件为: f[1] = 1

6
40
通过提交
时空限制2000ms/32mb
题目来源
评测方式在线评测
题目类型algorithm
难        度