题目描述
先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的差的绝对值都为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
Example1:
Input: 7 5 5 3 2 6 4 3 Output: 5
解题思路
- 简单dp
- 先排序，如果第二个比第一个大1的话 dp[i] = dp[i - 1] + 1
- 如果相等的话 dp[i] = dp[i - 1]
- 其他情况 dp[i] = 1
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> v(n, 0);
for(int i = 0; i < n; i++){
cin >> v[i];
}
sort(v.begin(), v.end());
int res = 1;
vector<int> dp(n, 0);
dp[0] = 1;
for(int i = 1; i < v.size(); i++){
if(v[i] - v[i - 1] == 1){
dp[i] = dp[i - 1] + 1;
}else if(v[i] == v[i - 1]){
dp[i] = dp[i - 1];
}else{
dp[i] = 1;
}
res = max(res, dp[i]);
}
cout << res << endl;
return 0;
}
