Mảng con có độ dài tối đa 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 ta được cung cấp một mảng có kích thước bất kỳ và nhiệm vụ là tìm mảng con của 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 - Mảng con có độ dài tối đa với sự khác biệt giữa các phần tử liền kề là 0 hoặc 1 là - 2

Giải thích - Các phần tử liền kề trong một mảng có chênh lệch 0 hoặc 1 là {2, 1}, {5, 6}, {3, 4} và {7.6}. Do đó, độ dài tối đa của mảng con là 2.

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

Đầu ra - Mảng con có độ dài tối đa 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ảng có chênh lệch 0 hoặc 1 là {2, 1} và {7, 6, 5} .. Do đó, độ dài tối đa của mảng 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 biến tạm thời i và đặt nó thành 0 và biến tối đa và đặt nó thành 0.
• Bắt đầu vòng lặp trong khi từ tôi đến kích thước của một mảng.
• Trong vòng lặp, đặt j thành i
• Bắt đầu một vòng lặp khác sẽ tính toán mảng con với các phần tử liền kề cho dù là 0 hay không.
• Bên trong vòng lặp, tăng giá trị của i.
• Đặt nhiệt độ thành i-j + 1
• Kiểm tra xem liệu tối đa có nhỏ hơn nhiệt độ hay không, sau đó đặt tối đa thành nhiệt độ.
• Kiểm tra xem liệu j có bằng với i hay không, sau đó tăng giá trị của i
• Trả lại số tiền tối đa
• In kết quả.

Ví dụ

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

Đầu vào

Maximum length subarray with difference between adjacent elements as either 0 or 1 are: 2