首页 > 试题广场 >

最长的可整合子数组的长度

[编程题]最长的可整合子数组的长度
  • 热度指数:16974 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
先给出可整合数组的定义:如果一个数组在排序之后,每相邻两个数的差的绝对值都为1,或者该数组长度为1,则该数组为可整合数组。例如,[5, 3, 4, 6, 2]排序后为[2, 3, 4, 5, 6],符合每相邻两个数差的绝对值都为1,所以这个数组为可整合数组
给定一个数组arr, 请返回其中最大可整合子数组的长度。例如,[5, 5, 3, 2, 6, 4, 3]的最大可整合子数组为[5, 3, 2, 6, 4],所以请返回5

数据范围:,数组中每个数都满足 

要求:时间复杂度为,空间复杂度为
进阶:时间复杂度 ,空间复杂度

注意:本题中子数组的定义是数组中连续的一段区间,例如 [1,2,3,4,5] 中 [2,3,4] 是子数组,[2,4,5] 和 [1,3] 不是子数组

输入描述:
第一行一个整数N,表示数组长度
第二行N个整数,分别表示数组内的元素


输出描述:
输出一个整数,表示最大可整合子数组的长度
示例1

输入

7
5 5 3 2 6 4 3

输出

5
示例2

输入

3
1 4 2

输出

1
n=eval(input())
t=list(map(eval,input().split()))
num=0
for i in range(len(t)):
    a=[]
    for j in range(len(t)-1,i,-1):
        a=t[i:j+1]
        b=list(set(a))
        if len(b)!=len(a):
            continue
        if len(a)<num:
            break
        if b[-1]-b[0]==len(b)-1:
            if len(b)>num:
                num=len(b)
                break
print(num)
一直超时,有什么好的办法吗?
发表于 2022-04-10 11:31:31 回复(0)