Độ dài tối đa của dãy con với sự khác biệt giữa các phần tử liền kề là 0 hoặc 1 | Đặt 2 trong C ++

Chúng tôi được cung cấp một mảng có kích thước bất kỳ và nhiệm vụ là tìm dãy con trong mảng đã cho với các phần tử có sự khác biệt giữa các phần tử liền kề là 0 hoặc 1.

Đầu vào - int arr [] ={2, 1, 5, 6, 3, 4, 7, 6}

Đầu ra - Độ dài tối đa của dãy con với sự khác biệt giữa các phần tử liền kề là 0 hoặc 1 là:3

Giải thích - Dãy con của các phần tử liền kề trong một mảng có hiệu là 0 hoặc 1 là {2, 1}. Do đó, độ dài tối đa của dãy con là 2.

Đầu vào - int arr [] ={2, 1, 7, 6, 5}

Đầu ra - Độ dài tối đa của dãy con với sự khác biệt giữa các phần tử liền kề là 0 hoặc 1 là:3

Giải thích - Các phần tử liền kề trong một mảng có hiệu số 0 hoặc 1 là {7, 6, 5} .. Do đó, độ dài tối đa của dãy con là 3.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nhập một mảng kiểu số nguyên có thể chứa các phần tử dương cũng như âm.

• Tính kích thước của một mảng và chuyển một mảng và kích thước cho hàm để có thêm chức năng.

• Lấy một biến tạm thời tối đa và đặt nó thành 0 và lấy một biến tạm thời khác và cũng đặt nó thành 0

• Tạo một biến un_map thuộc loại unsrdered_map

• Bắt đầu vòng lặp cho đến khi tôi nhỏ hơn kích thước

• Bên trong vòng lặp, đặt len ​​thành 0 và kiểm tra xem un_map.find (arr [i] -1)! =Un_map.end () &&len

• kiểm tra xem un_map.find (arr [i])! =un_map.end () &&len

• kiểm tra xem un_map.find (arr [i] +1)! =un_map.end () &&len

• Bây giờ đặt un_map [arr [i]] =len + 1

• Kiểm tra xem tối đa có nhỏ hơn un_map [arr [i]] hay không rồi đặt tối đa bằng un_map [arr [i]]

• Tăng giá trị của i

• Trả lại tối đa

• In kết quả

Ví dụ

#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;
}

Đầu ra

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