C++에서 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 시퀀스

우리는 모든 크기의 배열이 주어지며, 주어진 배열에서 인접 요소 간의 차이가 0 또는 1인 요소를 사용하여 하위 시퀀스를 찾는 작업을 수행합니다.

입력 - 정수 arr[] ={ 2, 1, 5, 6, 3, 4, 7, 6}

출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 수열은 − 3

설명 − 차이가 0 또는 1인 배열에서 인접한 요소의 부분열은 {2, 1}입니다. 따라서 하위 시퀀스의 최대 길이는 2입니다.

입력 - 정수 arr[] ={ 2, 1, 7, 6, 5}

출력 − 인접 요소 간의 차이가 0 또는 1인 최대 길이 부분 수열은 − 3

설명 − 차이가 0 또는 1인 배열의 인접 요소는 {7, 6, 5}입니다. 따라서 부분 수열의 최대 길이는 3입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• 양수 및 음수 요소를 모두 포함할 수 있는 정수 유형의 배열을 입력하세요.
• 배열의 크기를 계산하고 추가 기능을 위해 배열과 크기를 함수에 전달합니다.
• temp[크기]와 다른 변수의 최대값을 입력 배열과 동일한 크기로 임시 배열을 가져와서 0으로 설정합니다.
• 0부터 배열 크기까지 루프 시작
• 루프 내에서 temp[i]를 1로 설정
• 1에서 크기까지 다른 루프 시작
• 루프 내에서 0에서 i보다 작은 j까지 다른 루프 j 시작
• 루프 내부에서 차이가 0 또는 1인 인접한 요소가 있는지 확인한 다음 temp[i] + 1로 설정합니다.
• 0에서 크기까지 루프 시작
• 루프 내에서 최대값이 temp[i]보다 작은지 확인한 다음 maximum =temp[i]로 설정
• 최대 반환
• 결과 인쇄

예시

#include <bits/stdc++.h>
using namespace std;
//function to calculate the maximum difference
int maximum_adja(int arr[], int size){
   int temp[size], maximum = 0;
   for (int i=0; i<size; i++){
      temp[i] = 1;
   }
   for (int i=1; i<size; i++){
      for (int j=0; j<i; j++){
         if (abs(arr[i] - arr[j]) <= 1 && temp[i] < temp[j] + 1){
            temp[i] = temp[j] + 1;
         }
      }
   }
   for (int i=0; i<size; i++){
      if (maximum < temp[i]){
         maximum = temp[i];
      }
   }
   return maximum;
}
int main(){
   int arr[] = {1, 5, 3, 7, 8, 9, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum length subsequence with difference between adjacent elements as either 0
   or 1 is: "<<maximum_adja(arr, size);
   return 0;
}

출력

Maximum length subsequence with difference between adjacent elements as either 0 or 1 is: 3