양의 정수 배열이 제공됩니다. 목표는 그 안에 있는 연속적인 숫자의 최대 수를 찾는 것입니다. 우선 배열을 정렬한 다음 인접 요소 arr[j]==arr[i]+1(j=i+1)을 비교합니다. 차이가 1이면 카운트를 증가시키고 i++,j++ elsechange count=1을 인덱싱합니다. maxc에 지금까지 저장된 최대 개수를 저장합니다.
입력
Arr[]= { 100,21,24,73,22,23 } 출력
Maximum consecutive numbers in array : 4
설명 − 정렬된 배열은 − { 21,22,23,24,73,100 } initialize count=1,maxcount=1
1. 22=21+1 count=2 maxcount=2 i++,j++ 2. 23=22+2 count=3 maxcount=3 i++,j++ 3. 24=23+1 count=4 maxcount=4 i++,j++ 4. 73=24+1 X count=1 maxcount=4 i++,j++ 5. 100=73+1 X count=1 maxcount=4 i++,j++
최대 연속 번호는 4 { 21,22,23,24 }
입니다.입력
Arr[]= { 11,41,21,42,61,43,9,44 } 출력
Maximum consecutive numbers in array : 4
설명 − 정렬된 배열은 − { 9,11,21,41,42,43,44,61 } count=1,maxcount=1 초기화
1. 11=9+1 X count=1 maxcount=1 i++,j++ 2. 21=11+1 X count=1 maxcount=1 i++,j++ 3. 41=21+1 X count=1 maxcount=1 i++,j++ 4. 42=41+1 count=2 maxcount=2 i++,j++ 5. 43=42+1 count=3 maxcount=3 i++,j++ 6. 44=43+1 count=4 maxcount=4 i++,j++ 7. 61=44+1 X count=1 maxcount=4 i++,j++
최대 연속 번호는 4 { 41,42,43,44 }
입니다.아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 Arr[]은 정수를 저장하는 데 사용됩니다.
-
정수 'n'은 배열의 길이를 저장합니다.
-
subs( int arr[], int n) 함수는 배열의 크기를 입력으로 받아 배열에 있는 최대 연속 수를 반환합니다.
-
우선 sort(arr,arr+n)
를 사용하여 배열을 정렬합니다. -
이제 count=1 및 maxc=1을 초기화합니다.
-
두 개의 for 루프 내부의 처음 두 요소인 arr[0]과 arr[1]에서 시작하여 ifarr[j]==arr[i]+1( j=i+1)을 비교하고, true이면 count와 i를 다음만큼 증가시킵니다. 1.
-
위의 조건이 다시 거짓이면 count를 1로 변경합니다. 지금까지 발견된 가장 높은 count로 maxc를 업데이트합니다( maxc=count>maxc?count:maxc ).
-
결과적으로 최대 연속 요소 수로 maxc를 반환합니다.
예
#include <iostream>
#include <algorithm>
using namespace std;
int subs(int arr[],int n){
std::sort(arr,arr+n);
int count=1;
int maxc=1;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(arr[j]==arr[i]+1){
count++;
i++;
}
else
count=1;
maxc=count>maxc?count:maxc;
}
}
return maxc;
}
int main(){
int arr[] = { 10,9,8,7,3,2,1,4,5,6 };
int n = sizeof(arr) / sizeof(int);
cout << "Maximum consecutive numbers present in an array :"<<subs(arr, n);
return 0;
} 출력
Maximum consecutive numbers present in an array : 10