2023-07-27：最長可整合子數組的長度，

數組中的數字排序之后，相鄰兩數的差值是1，

這種數組就叫可整合數組。

給定一個數組，求最長可整合子數組的長度。

答案2023-07-27：

算法maxLen的過程如下：

1.檢查輸入數組是否為空，如果為空，則返回0，表示最長可整合子數組長度為0。

2.初始化長度為1的最長可整合子數組長度為ans。

3.創建一個空的set容器，用于記錄數組中的元素是否已經存在。

4.開始遍歷輸入數組，從start = 0開始。每次迭代，重置set為空。

5.初始化minVal和maxVal為arr[start]。

6.將arr[start]添加到set中，表示該元素已經存在。

7.開始從start+1位置向后遍歷數組，每次迭代的終止條件是end < len(arr)。

8.如果arr[end]在set中已經存在，表示遇到了重復元素，跳出循環。

9.將arr[end]添加到set中，表示該元素已經存在。

10.更新minVal和maxVal，如果arr[end]比minVal小，則更新minVal為arr[end]；如果arr[end]比maxVal大，則更新maxVal為arr[end]。

11.檢查當前子數組是否為可整合數組，即判斷maxVal和minVal之間的差值是否等于end-start。

12.如果當前子數組為可整合數組，更新ans為當前子數組長度和ans中較大的值。

13.返回最長可整合子數組長度ans。

算法right的過程如下：

1.檢查輸入數組是否為空，如果為空，則返回0，表示最長可整合子數組長度為0。

2.初始化ans為0，用于記錄最長可整合子數組的長度。

3.創建一個和輸入數組相同長度的輔助數組help。

4.開始從左邊界l開始遍歷數組，每次迭代，右邊界r從l開始向右遍歷數組。

5.將arr[l:r+1]拷貝到輔助數組help的對應位置。

6.對help數組的切片help[l:r+1]進行排序，將切片中的元素按從小到大的順序排列。

7.檢查排序后的help數組是否符合可整合數組的條件，即判斷help數組中相鄰元素之間的差值是否為1。

8.如果help數組滿足可整合數組條件，更新ans為當前子數組長度和ans中較大的值。

9.返回最長可整合子數組長度ans。

算法maxLen的時間復雜度和空間復雜度分別為：

時間復雜度：

- 最壞情況下，需要遍歷輸入數組中的每個元素，所以時間復雜度為O(n)，其中n是輸入數組的長度。

空間復雜度：

- 使用了一個set容器來存儲元素，所以空間復雜度為O(n)，其中n是輸入數組的長度。

算法right的時間復雜度和空間復雜度分別為：

時間復雜度：

- 最壞情況下，需要對每個子數組進行排序，對于長度為m的子數組，排序的時間復雜度為O(mlogm)。
- 因此，整個算法的時間復雜度為O(n^2 log n)，其中n是輸入數組的長度。

空間復雜度：

- 使用了一個輔助數組help存儲子數組的拷貝，所以空間復雜度為O(n)，其中n是輸入數組的長度。

# go完整代碼如下：

```go
package main

import (
    "fmt"
    "math"
    "math/rand"
    "sort"
)

func maxLen(arr []int) int {
    if arr == nil || len(arr) == 0 {
        return 0
    }
    ans := 1
    set := make(map[int]bool)
    for start := 0; start < len(arr); start++ {
        set = make(map[int]bool)
        minVal := arr[start]
        maxVal := arr[start]
        set[arr[start]] = true
        for end := start + 1; end < len(arr); end++ {
            if set[arr[end]] {
                break
            }
            set[arr[end]] = true
            if arr[end] < minVal {
                minVal = arr[end]
            }
            if arr[end] > maxVal {
                maxVal = arr[end]
            }
            if maxVal-minVal == end-start {
                ans = int(math.Max(float64(end-start+1), float64(ans)))
            }
        }
    }
    return ans
}

func right(arr []int) int {
    if arr == nil || len(arr) == 0 {
        return 0
    }
    n := len(arr)
    ans := 0
    help := make([]int, n)
    for l := 0; l < n; l++ {
        for r := l; r < n; r++ {
            copy(help[l:r+1], arr[l:r+1])
            sort.Ints(help[l : r+1])
            ok := true
            for i := l + 1; i <= r; i++ {
                if help[i-1]+1 != help[i] {
                    ok = false
                    break
                }
            }
            if ok {
                ans = int(math.Max(float64(ans), float64(r-l+1)))
            }
        }
    }
    return ans
}

func randomArray(n, v int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = rand.Intn(v) + 1
    }
    return arr
}

func main() {
    N := 100
    V := 50
    testTimes := 10000
    fmt.Println("測試開始")
    for i := 0; i < testTimes; i++ {
        n := rand.Intn(N)
        arr := randomArray(n, V)
        ans1 := maxLen(arr)
        ans2 := right(arr)
        if ans1 != ans2 {
            fmt.Println("出錯了!")
        }
    }
    fmt.Println("測試結束")
}
```


# c++完整代碼如下：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

int maxLen(vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }
    int ans = 1;
    unordered_set<int> set;
    for (int start = 0; start < arr.size(); start++) {
        set.clear();
        int minVal = arr[start];
        int maxVal = arr[start];
        set.insert(arr[start]);
        for (int end = start + 1; end < arr.size(); end++) {
            if (set.find(arr[end]) != set.end()) {
                break;
            }
            set.insert(arr[end]);
            minVal = min(minVal, arr[end]);
            maxVal = max(maxVal, arr[end]);
            if (maxVal - minVal == end - start) {
                ans = max(ans, end - start + 1);
            }
        }
    }
    return ans;
}

int right(vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }
    int n = arr.size();
    int ans = 0;
    vector<int> help(n);
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            for (int i = l; i <= r; i++) {
                help[i] = arr[i];
            }
            sort(help.begin() + l, help.begin() + r + 1);
            bool ok = true;
            for (int i = l + 1; i <= r; i++) {
                if (help[i - 1] + 1 != help[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans = max(ans, r - l + 1);
            }
        }
    }
    return ans;
}

vector<int> randomArray(int n, int v) {
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = rand() % v + 1;
    }
    return ans;
}

int main() {
    int N = 100;
    int V = 50;
    int testTimes = 10000;
    cout << "測試開始" << endl;
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N;
        vector<int> arr = randomArray(n, V);
        int ans1 = maxLen(arr);
        int ans2 = right(arr);
        if (ans1 != ans2) {
            cout << "出錯了!" << endl;
        }
    }
    cout << "測試結束" << endl;
    return 0;
}
```