给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6.

输入描述:
第一行包含一个整数T,代表测试数据组数。
对于每组测试数据: N-数组的长度
a1 a2 … an (需要计算的数组)
保证: 1<=N<=3000,0<=ai<=MAX_INT.

输出描述:
对于每组数据,输出一个整数,代表最长递增子序列的长度。

输入例子:
2
7
89 256 78 1 46 78 8
5
6 4 8 2 17

输出例子:
3
3

1 2 收藏


直接登录
最新评论
  • 王念一 高一学生 2016/09/13

    这样。

    (只是思路,懒得实现)

  • 袁言 工程师 2016/09/14

    python consts.py
    (6, [1, 3, 5, 6, 7, 8])
    (6, [1, 2, 4, 6, 7, 8])
    (3, [1, 46, 78])

     

  • cuzfinal   2016/09/14

    动态规划的题目。

  • 喝茶去 程序员 2016/09/16

    什么鬼都要dp?搞siao!

  • fu昀 软件工程师 2016/09/16

    若需要严格递增,则将排好序的数组去重即可

  • 抛砖引玉,楼上都是基于O(n^2)的dp的方法,在很多OJ上,这样的方法是通不过的,推荐使用基于二分搜索的方法。其中bs[i]代表,长度为i的递增子序列最后一个元素最小是多少。当然,这里适合没有重复元素的情况。

  • 王先生 学生 2016/09/21

    自己写了一个,用的动态规划