给定长度为 N 的正整数序列 x1 ,x2 ,…,xn 。寻找它的一个最长子序列,使得子序列是不下降的,输出此子序列的长度。
8 1 3 1 5 9 7 4 8
5
定义 f [i] 表示在取第 i 个数时,前 i 个数的最长不下降子序列的最大长度,状态转移方程为:
f[i] = max{ f[j] } + 1(j
边界条件为: f[1] = 1