우리는 모든 크기의 배열이 주어지고 인접한 요소 사이의 차이가 0 또는 1인 요소를 사용하여 주어진 배열의 하위 배열을 찾는 작업을 수행합니다.
입력 - 정수 arr[] ={ 2, 1, 5, 6, 3, 4, 7, 6}
출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 하위 배열은 − 2
설명 − 차이가 0 또는 1인 배열의 인접 요소는 {2, 1}, {5, 6}, { 3, 4} 및 {7.6}입니다. 따라서 하위 배열의 최대 길이는 2입니다.
입력 - 정수 arr[] ={ 2, 1, 7, 6, 5}
출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 하위 배열은 − 3
설명 − 차이가 0 또는 1인 배열의 인접 요소는 {2, 1} 및 {7, 6, 5}입니다. 따라서 하위 배열의 최대 길이는 3입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 양수 및 음수 요소를 모두 포함할 수 있는 정수 유형의 배열을 입력하세요.
- 배열의 크기를 계산하고 추가 기능을 위해 배열과 크기를 함수에 전달합니다.
- 임시 변수 i를 0으로 설정하고 최대 변수를 0으로 설정합니다.
- i부터 배열의 크기까지 while 루프를 시작합니다.
- 루프 내에서 j를 i로 설정
- 0인지 아닌지에 관계없이 인접한 요소로 하위 배열을 계산하는 또 다른 루프를 시작합니다.
- 루프 내에서 i 값을 증가시킵니다.
- 온도를 i-j+1로 설정
- 최대값이 temp보다 작은지 확인한 다음 최대값을 temp로 설정합니다.
- j가 i와 같은지 확인한 다음 i의 값을 증가시킵니다.
- 최대값 반환
- 결과를 인쇄합니다.
예
#include<bits/stdc++.h>
using namespace std;
//function to calculate maximum Length subarray with
// 0 or 1 difference between adjacent elements
int maximum_diff(int arr[], int size){
int i = 0;
int maximum = 0;
while (i < size){
int j = i;
while (i+1 < size && (abs(arr[i] - arr[i + 1]) == 1 || abs(arr[i] - arr[i + 1]) == 0)){
i++;
}
int temp = i - j + 1;
if (maximum < temp){
maximum = temp;
}
if(j == i){
i++;
}
}
return maximum;
}
int main(){
int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum length subarray with difference between adjacent elements as either 0 or 1
are: "<< maximum_diff(arr, size);
} 입력
Maximum length subarray with difference between adjacent elements as either 0 or 1 are: 2