A23724. 最长连续段
填空题
较难
知识点
题目描述
最长连续段
题目描述
对于 k个整数构成的数组[b1,b2,...,bk] ，如果对1≤i＜k 都有bi+1=bi+1 ，那么称数组 b是一个连续段。
给定由n 个整数构成的数组[a1,a2,...,an] ，你可以任意重排数组 a中元素顺序。请问在重排顺序之后，a 所有是连续段的子数组中，最长的子数组长度是多少？
例如，对于数组 [1,0,2,4]，可以将其重排为[4,0,1,2] ，有以下10 个子数组：
[4], [0], [1], [2], [4,0], [0,1], [1,2], [4,0,1], [0,1,2], [4,0,1,2]
其中除 [4,0], [4,0,1], [4,0,1,2] 以外的子数组均是连续段，因此是连续段的子数组中，最长子数组长度为 3。
输入格式
第一行，一个正整数 n，表示数组长度。
第二行， n个整数a1,a2,...,an ，表示数组中的整数。
输出格式
一行，一个整数，表示数组 a重排顺序后，所有是连续段的子数组的最长长度。
样例
输入样例 1
4
1 0 2 4输出样例 1
3输入样例 2
9
9 9 8 2 4 4 3 5 3输出样例 2
4数据范围
对于 40% 的测试点，保证1≤n≤8。
对于所有测试点，保证1≤n≤105 ，-109≤ai≤109 。
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N];
int last, cnt, mx;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + n + 1);
last = a[1];
cnt = mx = 1;
for (int i = 1; i <= n; i++) {
if (a[i] == last) continue;
if (a[i] == last + 1)
cnt++;
else
cnt = 1;
last = a[i];
mx = max(cnt, mx);
}
printf("%d\n", mx);
return 0;
}
上一题
下一题