题目：先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的差的绝对值都为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。要求时间复杂度为O(n2)O(n^2)O(n2)，空间复杂度为O(n)O(n)O(n)。
输入描述:
第一行一个整数N，表示数组长度
第二行N个整数，分别表示数组内的元素
输出描述:
输出一个整数，表示最大可整合子数组的长度
例1
输入
7
5 5 3 2 6 4 3
输出
5
分析：采用快速排序的算法，再遍历一遍数组，即可取得答案。
code：
n = int(input())
arr = list(map(int, input().split()))
def quick_sort(lists, left, right):
if left > right:
return lists
key = lists[left]
low = left
high = right
while left < right:
if left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
if left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
lis = quick_sort(arr, 0, len(arr) - 1)
if arr == []:
print(0)
else:
max_length, l = 1, 1
for i in range(1,n):
if lis[i] - lis[i-1] == 1:
l += 1
else:
if l > max_length:
max_length = l
l = 1
else:
l = 1
print(max_length)
程序输出的结果：
5
网友评论