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

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

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

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

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

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

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

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

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

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

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

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

// ฟังก์ชันคำนวณความยาว subsequence สูงสุด
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;
}

ผลลัพธ์

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