ลำดับ Palindromic ที่ยาวที่สุด

ลำดับย่อย Palindromic ที่ยาวที่สุดคือลำดับย่อยของลำดับที่กำหนด และลำดับต่อมาคือ Palindrome

ในปัญหานี้ เราได้ให้ลำดับอักขระหนึ่งชุด เราต้องหาความยาวที่ยาวที่สุดของลำดับย่อยพาลินโดรม

ในการแก้ปัญหานี้ เราสามารถใช้สูตรแบบเรียกซ้ำได้

ถ้า L (0, n-1) ถูกใช้เพื่อเก็บความยาวของลำดับย่อยพาลินโดรมที่ยาวที่สุด ดังนั้น
L (0, n-1) :=L (1, n-2) + 2 (เมื่ออักขระที่ 0 และ (n-1)' เหมือนกัน)

อินพุตและเอาต์พุต

Input:สตริงที่มีตัวอักษรหรือสัญลักษณ์ต่างกัน สมมติว่าอินพุตคือ “ABCDEEAB” เอาต์พุต:ความยาวที่ยาวที่สุดของลำดับย่อยพาลินโดรมที่ใหญ่ที่สุด นี่คือ 4.ABCDEEAB ดังนั้น palindrome คือ AEEA

อัลกอริทึม

palSubSeqLen(str)

ป้อนข้อมูล - สตริงที่กำหนด

ผลลัพธ์ − ความยาวของลำดับย่อยพาลินโดรมที่ยาวที่สุด

เริ่มต้น n =ความยาวของสตริง สร้างตารางชื่อ lenTable ขนาด n x n และเติม 1s สำหรับ col :=2 ถึง n ทำเพื่อ i :=0 ถึง n – col ทำ j :=i + col – 1 ถ้า str[i] =str[j] และ col =2 แล้ว lenTable[i, j] :=2 อื่น ๆ ถ้า str[i] =str[j] แล้ว lenTable[i, j] :=lenTable[i+ 1, j-1] + 2 อื่น ๆ lenTable[i, j] :=สูงสุดของ lenTable[i, j-1] และ lenTable[i+1, j] เสร็จแล้ว ส่งคืน lenTable[0, n-1]End 
ตัวอย่าง
 
#includeใช้เนมสเปซ std;int max (int x, int y) { return (x> y)? x :y;}int palSubseqLen (สตริง str) { int n =str.size (); int lenTable[n][n]; // สร้างตารางเพื่อเก็บผลลัพธ์ของปัญหาย่อยสำหรับ (int i =0; i  
ผลลัพธ์
 
ความยาวของลำดับย่อย palindrome ที่ยาวที่สุดคือ:4