程序员代码面试指南---002最长的可整合子数组的长度

题目描述

先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的差的绝对值都为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(n^2)O(n2)，空间复杂度为O(n)

输入描述

第一行一个整数N，表示数组长度
第二行N个整数，分别表示数组内的元素

输出描述

输出一个整数，表示最大可整合子数组的长度

示例

输入
7
5 5 3 2 6 4 3
输出
5

解题思路

如果一个无重复数字的数组中，最大值-最小值+1=数组长度，那么这个数组就是可整合的。
比如：
数组1,2,3,4,5
5-1+1=5。则这个数组是可以整合的，且最大长度为5。

代码实现

/*
 * @Description: 最长的可整合的数组的长度
 * @Author: 
 * @Date: 2020-10-15 20:12:51
 * @LastEditTime: 2020-10-15 20:43:14
 * @LastEditors: Please set LastEditors
 */
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int N = 0; //N表示数组的长度
    int num = 0;//数组中每一个数字
    cin >> N;
    if(N <= 1){
        cout << N <<endl;
        return 0;
    }
    vector<int> arr;
    for(int i = 0;i < N;i++){
        cin >> num;
        arr.push_back(num);
    }
    vector<int> result;
    for(int i = 0;i < arr.size();i++){
        int max_num = arr[i];
        int min_num = arr[i];
        for(int j = i + 1;j < arr.size();j++){
            max_num = max(max_num, arr[j]);
            min_num = min(min_num, arr[j]);
            if(max_num - min_num == j - i){//核心代码
                result.push_back(max_num - min_num + 1);
            }
        }
    }
    sort(result.begin(), result.end()); //将最大长度排在最后
    cout << result.back() << endl; //取出最后一个元素
    //system("pause");
    return 0;
}