最长递增子序列A

[编程题]最长递增子序列A

热度指数：3465 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个长度为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.

输出描述:

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

示例1

输入

2
7
89 256 78 1 46 78 8
5
6 4 8 2 17

输出

3
3

算法知识视频讲解

查看答案及解析

Python

牛客156465号

def compute_sub_max(num_list):
result_list = [1]
for i, one_num in enumerate(num_list[1:]): # 找到以第i个位置结尾的最长子串长度
i += 1
max_len = 1
while i >= 0:
if num_list[i] < one_num:
max_len = max(max_len, result_list[i] + 1)
i -= 1
result_list.append(max_len)
return max(result_list)

num_group = int(raw_input())
while num_group > 0:
raw_input()
print compute_sub_max(map(int, raw_input().split()))
num_group -= 1

发表于 2019-04-14 17:25:02 回复(0)