程序员代码面试指南 002

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

题目要求O(n ^ 2)的复杂度。使用二重循环将子数组枚举出来就已经够了，所以应该是在枚举的过程中就要判断是否可以整合。可整合的数组在排序后是一个公差为1的等差数列，因此直接判断子数组的极差是否和下标范围相等即可。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N = 0;
    cin >> N;
    vector<int> vec(N, 0);
    for(int i = 0; i < N; i++)
    {
        cin >> vec[i];
    }
    int len = 1, min, max;
    for(int i = 0; i < N; i++)
    {
        min = max = vec[i];
        for(int j = i + 1; j < N; j++)
        {
            if(vec[j] < min) min = vec[j];
            if(vec[j] > max) max = vec[j];
            if(max - min == j - i){
                if(len < j - i + 1){
                    len = j - i + 1;
                }
            }
        }
    }
    cout << len << endl;
}