Độ 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 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 mảng tạm thời có cùng kích thước với mảng đầu vào, giả sử như tạm thời [kích thước] và giá trị tối đa có thể thay đổi khác và đặt nó thành 0
• Bắt đầu vòng lặp cho từ 0 đến kích thước của một mảng
• Trong vòng lặp, hãy đặt nhiệt độ [i] bằng 1
• Bắt đầu một vòng lặp khác, từ 1 đến kích thước
• Bên trong vòng lặp, bắt đầu một vòng lặp khác j từ 0 cho đến khi j nhỏ hơn i
• Bên trong vòng lặp, hãy kiểm tra xem liệu các phần tử liền kề có chênh lệch 0 hoặc 1 hay không, sau đó settemp [i] với temp [i] + 1
• Bắt đầu vòng lặp cho từ 0 đến kích thước
• Bên trong vòng lặp, hãy kiểm tra xem giá trị tối đa có nhỏ hơn nhiệt độ [i] hay không, sau đó đặt giá trị tối đa =nhiệt độ [i]
• Lợi nhuận tối đa
• In kết quả

Ví dụ

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

Đầu ra

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