ความยาว Subsequence สูงสุดที่ความต่างระหว่างติดกันเป็น 0 หรือ 1 | ชุดที่ 2 ใน 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} ดังนั้นความยาวสูงสุดคือ 3

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

• รับอินพุตอาร์เรย์ประเภทจำนวนเต็ม ที่อาจมีทั้งบวกและลบ
• คำนวณขนาดอาร์เรย์ ส่งเข้าไปฟังก์ชันเพื่อประมวลผลต่อ
• ตัวแปร maximum = 0, i = 0
• สร้างตัวแปร un_map ประเภท unordered_map
• While loop จน i < size
• ในลูป ตั้ง len = 0 ตรวจสอบ un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1] แล้ว len = un_map[arr[i]-1]
• ตรวจสอบ un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]] แล้ว len = un_map[arr[i]]
• ตรวจสอบ un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1] แล้ว len = un_map[arr[i]+1]
• ตั้ง un_map[arr[i]] = len + 1
• ถ้า maximum < un_map[arr[i]] ตั้ง maximum = un_map[arr[i]]
• i++
• คืนค่า maximum
• พิมพ์ผลลัพธ์

ตัวอย่างโปรแกรม

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

// คำนวณ subsequence สูงสุด
int maximum_adj(int arr[], int size) {
    int maximum = 0, i = 0;
    unordered_map<int, int> un_map;
    while(i < size) {
        int len = 0;
        if (un_map.find(arr[i] - 1) != un_map.end() && len < un_map[arr[i] - 1]) {
            len = un_map[arr[i] - 1];
        }
        if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]) {
            len = un_map[arr[i]];
        }
        if (un_map.find(arr[i] + 1) != un_map.end() && len < un_map[arr[i] + 1]) {
            len = un_map[arr[i] + 1];
        }
        un_map[arr[i]] = len + 1;
        if (maximum < un_map[arr[i]]) {
            maximum = un_map[arr[i]];
        }
        i++;
    }
    return maximum;
}

int main() {
    int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: " << maximum_adj(arr, size);
    return 0;
}

เอาต์พุต

Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4