P1049最长不下降子序列的长度

题目描述

设有由n个不相同的整数组成的数列,记为:

a[1],a[2],...,a[n]且a[i]<>a[j] [i<>j]
若存在i1<i2<i3,...,<ik且有a[i1]<a[i2]<...<a[ik],则称为长度为k的不下降子序列.

整数组成的数列为3,18,7,14,10,12,23,41,16,24.
则3,18,23,24就是一个长度为4的不下降子序列.
同时还有3,7,10,12,23,41和3,7,10,12,16,24都是长度为6的最长不下降子序列.

给定一个序列，求最长不下降子序列的长度

输入

第一行为n，表示n个数 第二行n个数

输出

最长不下降子序列的长度

样例

提示

N小于5000

for  each  num  < =maxint

令mem[i]表示以a[i]结尾的最长不下降子序列长度。这样对a[i]来说就会有两种可能：
1、如果存在a[i]之前的元素a[j]（j < i），使得a[j] <= a[i]并且mem[j] + 1 > mem[i]（即把a[i]放在前面那个以a[j]结尾的不降子序列的后面使得新得到的子序列比原来以a[i]结尾的子序列更长）；
2、如果不存在a[j]使得a[j] <= a[i] (j < i)，那么以a[i]结尾的不降子序列就只包含a[i]一个数字，因此mem[i] = 1.

来源/分类