ลำดับย่อยความยาวสูงสุดโดยมีความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันเป็น 0 หรือ 1 | ชุดที่ 2 ใน C++

เราได้รับอาร์เรย์ทุกขนาดและภารกิจคือการค้นหาลำดับต่อในอาร์เรย์ที่กำหนดโดยองค์ประกอบที่มีความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันเป็น 0 หรือ 1

ป้อนข้อมูล − int arr[] ={ 2, 1, 5, 6, 3, 4, 7, 6}

ผลผลิต − ลำดับย่อยความยาวสูงสุดโดยมีความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันเป็น 0 หรือ 1 คือ:3

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

ป้อนข้อมูล − int arr[] ={ 2, 1, 7, 6, 5}

ผลผลิต − ลำดับย่อยความยาวสูงสุดโดยมีความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันเป็น 0 หรือ 1 คือ:3

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

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

• ป้อนอาร์เรย์ของจำนวนเต็มประเภทซึ่งสามารถประกอบด้วยองค์ประกอบบวกและลบได้

• คำนวณขนาดของอาร์เรย์และส่งอาร์เรย์และขนาดไปยังฟังก์ชันเพื่อการทำงานต่อไป

• ใช้ตัวแปรสูงสุดชั่วคราวและตั้งค่าเป็น 0 และใช้ตัวแปรชั่วคราวอื่นและตั้งค่าเป็น 0 เช่นกัน

• สร้างตัวแปร un_map ของประเภท unordered_map

• เริ่มวนซ้ำในขณะที่ฉันน้อยกว่าขนาด

• ภายในลูป ตั้งค่า len เป็น 0 และตรวจสอบว่า un_map.find(arr[i]-1) !=un_map.end() &&len

• ตรวจสอบว่า un_map.find(arr[i]) !=un_map.end() &&len

• ตรวจสอบว่า un_map.find(arr[i]+1) !=un_map.end() &&len

• ตอนนี้ตั้งค่า un_map[arr[i]] =len + 1

• ตรวจสอบว่าสูงสุดน้อยกว่า un_map[arr[i]] แล้วตั้งค่าสูงสุดด้วย un_map[arr[i]]

• เพิ่มค่าของ i

• ผลตอบแทนสูงสุด

• พิมพ์ผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
//calculate the maximum 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