อัลกอริทึมค้นหา subarray ยาวที่สุดที่ผลต่างระหว่างสมาชิกติดกันเป็น 0 หรือ 1 ใน C++

เราได้รับอาเรย์ขนาดเท่าใดก็ตาม และงานคือการหา subarray ของอาเรย์ที่กำหนดซึ่งสมาชิกมีผลต่างระหว่างสมาชิกติดกันเป็น 0 หรือ 1

อินพุต − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6 }

เอาต์พุต − Maximum length subarray with difference between adjacent elements as either 0 or 1 are − 2

คำอธิบาย − สมาชิกติดกันในอาเรย์ที่มีผลต่างเป็น 0 หรือ 1 คือ {2, 1}, {5, 6}, {3, 4} และ {7, 6} ดังนั้นความยาวสูงสุดของ subarray คือ 2

อินพุต − int arr[] = { 2, 1, 7, 6, 5 }

เอาต์พุต − Maximum length subarray with difference between adjacent elements as either 0 or 1 are − 3

คำอธิบาย − สมาชิกติดกันในอาเรย์ที่มีผลต่างเป็น 0 หรือ 1 คือ {2, 1} และ {7, 6, 5} ดังนั้นความยาวสูงสุดของ subarray คือ 3

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• รับอินพุตเป็นอาเรย์จำนวนเต็ม ซึ่งอาจมีทั้งจำนวนบวกและลบ
• คำนวณขนาดของอาเรย์และส่งอาเรย์พร้อมขนาดไปยังฟังก์ชัน
• ใช้ตัวแปรชั่วคราว i = 0 และ maximum = 0
• เริ่มลูป while จาก i ถึงขนาดของอาเรย์
• ภายในลูป กำหนด j = i
• เริ่มลูปอีกอันหนึ่งเพื่อคำนวณ subarray ที่สมาชิกติดกันมีผลต่าง 0 หรือ 1
• ภายในลูป เพิ่มค่า i
• กำหนด temp = i - j + 1
• ตรวจสอบว่า maximum น้อยกว่า temp ให้กำหนด maximum = temp
• ตรวจสอบว่าหาก j เท่ากับ i ให้เพิ่มค่า i
• คืนค่า maximum
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด

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

// ฟังก์ชันคำนวณความยาว subarray สูงสุดที่ผลต่างสมาชิกติดกันเป็น 0 หรือ 1
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);
    return 0;
}

ผลลัพธ์

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