首页 > 试题广场 >

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

[编程题]求最长可整合子数组的长度
  • 热度指数:428 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
先给出可整合数组的定义: 如果一个数组arr在排序之后,从最小值到最大值的顺序中,每相邻两个数之间差的绝对值都为1,则arr为可整合数组。 例如: arr = {5,3,4,6,2},再排序之后为:{2,3,4,5,6},排序后符合每相邻两个数之间差的绝对值都为1,所以arr是可整合数组。 给定一个整形数组arr,请返回其中长度最大的可整合子数组的长度。
[5,0,1,2,4,3,9],最长可整合子数组为[5,0,1,2,4,3],所以返回6
[6,7,3,0,1,2,4,7],最长可整合子数组为[3,0,1,2,4],所以返回5
 要求:如果数组长度为N,时间复杂度请达到O(N^2)

这道题你会答吗?花几分钟告诉大家答案吧!