Dãy con dài nhất có hiệu giữa các phần tử liền kề bằng 0 hoặc 1 trong C++

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

Ví dụ

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

Đầu ra − Độ dài dãy con tối đa với hiệu 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ảng với 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 dãy con tối đa với hiệu 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 với hiệu là 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 sử dụng trong chương trình dưới đây

• Nhập một mảng kiểu số nguyên có thể chứa cả phần tử dương và âm.
• Tính kích thước của mảng và truyền mảng cùng kích thước cho hàm để xử lý tiếp.
• Tạo một mảng tạm thời cùng kích thước với mảng đầu vào, ví dụ temp[size], và một biến maximum gán giá trị 0.
• Vòng lặp for từ 0 đến kích thước mảng.
• Trong vòng lặp, gán temp[i] = 1.
• Vòng lặp for thứ hai từ 1 đến size.
• Trong vòng lặp, vòng lặp thứ ba j từ 0 đến j < i.
• Trong vòng lặp, kiểm tra nếu các phần tử liền kề có hiệu 0 hoặc 1 thì gán temp[i] = temp[i] + 1.
• Vòng lặp for từ 0 đến size.
• Trong vòng lặp, kiểm tra nếu maximum < temp[i] thì gán maximum = temp[i].
• Trả về maximum.
• In kết quả.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

// Hàm tính độ dài dãy con tối đa
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 << "Độ dài dãy con tối đa với hiệu giữa các phần tử liền kề là 0 hoặc 1: " 
         << maximum_adja(arr, size); 
    return 0; 
}

Kết quả

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