数组与矩阵---最长可整合子数组的长度

【题目】

　　先给出可整合数组的定义。如果一个数组在排序后，每相邻两个数的差的绝对值都是1，则该数组为可整合数组。例如，[5,3,4,6,2]排序之后为[2,3,4,5,6]，符合条件，所以这个数组为可整合数组。
　　给定一个整型数组arr，请返回其中最大可整合子数组的长度。例如，[5,5,3,2,6,4,3]的最大可整合子数组为[5,3,2,6,4]，所以返回5

【基本思路】

　　方法一。时间复杂度O(N^3 logN)。
　　穷举每一种子数组情况，然后对每一个子数组排序，判断是否满足可整合数组的条件即可。特别注意：在处理子数组的时候要复制一个新的数组，不能改变数组中原有的位置。一共有N^2个子数组，排序的时间复杂度是O(logN)，所以总的时间复杂度是O(N^3logN)。

下面是使用python3.5实现的代码：

def getMaxIntegratedLength(arr):
    def isIntergrated(arr):
        arr.sort()  #切片产生的是新列表，不需要克隆
        for i in range(1, len(arr)):
            if arr[i]-arr[i-1] != 1:
                return False
        return True

    if arr == None or len(arr) == 0:
        return 0
    length = 0
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            if isIntergrated(arr[i : j+1]):
                length = max(length, j-i+1)
    return length

　　
　　方法二。时间复杂度O(N^2)。
　　依旧是穷举每一个子数组，但是在判断子数组是否是可整合数组时并不采用排序的方法，而是采用如下方法：

1. 判断子数组中是否有重复元素，如果有，肯定不是可整合数组。这个过程可以使用哈希表完成。

2. 找到子数组中的最大值max和最小值min，及其相应的下表 i 和 j ，如果 max - min == j - i，则该子数组一定是可整合数组；否则不是。

这个过程的时间复杂度O(1)，所有整体的时间复杂度是O(N^2)。实现代码如下：

def getMaxIntegratedLength2(arr):
    if arr == None or len(arr) == 0:
        return 0
    length = 0
    map = {}
    for i in range(len(arr)):
        maxEle = -sys.maxsize
        minEle = sys.maxsize
        for j in range(i, len(arr)):
            if arr[j] in map:
                break
            map[arr[j]] = 1
            maxEle = max(maxEle, arr[j])
            minEle = min(minEle, arr[j])
            if maxEle - minEle == j - i:
                length = max(length, j - i + 1)
        map.clear()
    return length