Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

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

<시간/>

우리는 모든 크기의 배열이 주어지며, 주어진 배열에서 인접 요소 간의 차이가 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입니다.

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

  • 양수 요소와 음수 요소를 모두 포함할 수 있는 정수 유형의 배열을 입력하십시오.

  • 배열의 크기를 계산하고 추가 기능을 위해 배열과 크기를 함수에 전달합니다.

  • 임시 변수 최대값을 가져 와서 0으로 설정하고 다른 임시 변수를 가져 와서 0으로 설정하십시오.

  • unordered_map 유형의 변수 un_map 생성

  • 내가 크기보다 작아질 때까지 루프 시작

  • 루프 내에서 len을 0으로 설정하고 un_map.find(arr[i]-1) !=un_map.end() &&len

  • 확인 un_map.find(arr[i]) !=un_map.end() &&len 설정

  • 확인 un_map.find(arr[i]+1) !=un_map.end() &&len 설정

  • 이제 un_map[arr[i]] =len + 1

    을 설정합니다.

  • 최대값이 un_map[arr[i]]보다 작은지 확인한 다음 un_map[arr[i]]

    으로 최대값을 설정합니다.

  • i의 값 증가

  • 최대 반환

  • 결과 인쇄

예시

#include <bits/stdc++.h>
using namespace std;
//calculate the maximum subsequence
int maximum_adj(int arr[], int size){
   int maximum = 0, i = 0;
   unordered_map<int, int> un_map;
   while(i < size){
      int len = 0;
      if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]){
         len = un_map[arr[i]-1];
      }
      if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]){
         len = un_map[arr[i]];
      }
      if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]){
         len = un_map[arr[i]+1];
      }
      un_map[arr[i]] = len + 1;
      if (maximum < un_map[arr[i]]){
         maximum = un_map[arr[i]];
      }
      i++;
   }
   return maximum;
}
int main(){
   int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum length subsequence with difference between adjacent elements as either 0
   or 1 are: "<< maximum_adj(arr, size);
   return 0;
}

출력

Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4