เราได้รับอาร์เรย์ทุกขนาดและภารกิจคือการค้นหาลำดับต่อในอาร์เรย์ที่กำหนดโดยองค์ประกอบที่มีความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันเป็น 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
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- ป้อนอาร์เรย์ของจำนวนเต็มประเภทซึ่งสามารถประกอบด้วยองค์ประกอบบวกและลบได้
- คำนวณขนาดของอาร์เรย์และส่งอาร์เรย์และขนาดไปยังฟังก์ชันเพื่อการทำงานเพิ่มเติม
- ใช้อาร์เรย์ชั่วคราวที่มีขนาดเท่ากันของอาร์เรย์อินพุต สมมุติว่า temp[size] และค่าสูงสุดอื่น และตั้งค่าเป็น 0
- เริ่มการวนซ้ำตั้งแต่ 0 จนถึงขนาดของอาร์เรย์
- ภายในลูป ตั้งค่า temp[i] ด้วย 1
- เริ่มลูปใหม่ตั้งแต่ 1 จนถึงขนาด
- ภายในลูป เริ่มวนใหม่อีกครั้งตั้งแต่ 0 ถึง j น้อยกว่า i
- ภายในลูป ให้ตรวจสอบว่าองค์ประกอบที่อยู่ติดกันมีความแตกต่าง 0 หรือ 1 จากนั้น settemp[i] กับ temp[i] + 1
- เริ่มการวนซ้ำตั้งแต่ 0 จนถึงขนาด
- ภายในลูป ให้ตรวจสอบว่าค่าสูงสุดน้อยกว่า temp[i] แล้วตั้งค่า maximum =temp[i]
- ผลตอบแทนสูงสุด
- พิมพ์ผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
//function to calculate the maximum difference
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
