ผลสืบเนื่องที่ยาวที่สุด

ลำดับย่อยทั่วไปที่ยาวที่สุดคือประเภทของลำดับย่อยซึ่งมีอยู่ในทั้งลำดับหรืออาร์เรย์ที่กำหนด

เราจะเห็นได้ว่ามีปัญหาย่อยมากมายซึ่งถูกคำนวณซ้ำแล้วซ้ำเล่าเพื่อแก้ปัญหานี้ ด้วยการใช้คุณสมบัติโครงสร้างย่อยที่ทับซ้อนกันของการเขียนโปรแกรมไดนามิก เราสามารถเอาชนะความพยายามในการคำนวณได้ เมื่อคำนวณผลลัพธ์ของปัญหาย่อยและจัดเก็บไว้ในตารางแล้ว เราก็สามารถคำนวณผลลัพธ์ถัดไปโดยใช้ผลลัพธ์ก่อนหน้าได้

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

Input:
Two strings with different letters or symbols.
string 1: AGGTAB
string 2: GXTXAYB
Output:
The length of the longest common subsequence. Here it is 4.
AGGTAB and GXTXAYB. The underlined letters are present in both strings and in correct sequence.

อัลกอริทึม

longestComSubSeq(str1, str2)

อินพุต - 2 strings เพื่อค้นหาความยาวของ Longest Common Subsequence

ผลลัพธ์ - ความยาวของ LCS

Begin
   m := length of str1
   n := length of str2
   define longSubSeq matrix of order (m+1) x (n+1)

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0 or j = 0, then
           longSubSeq[i,j] := 0
         else if str1[i-1] = str2[j-1], then
            longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
         else
            longSubSeq[i,j] := maximum of longSubSeq[i-1, j] and
            longSubSeq[i, j-1]
      done
   done

   longSubSeq[m, n]
End

ตัวอย่าง

#include<iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a : b;
}

int longestComSs( string str1, string str2) {
   int m = str1.size();
   int n = str2.size();
   
   int longSubSeq[m+1][n+1];
   
   //longSubSeq[i,j] will hold the LCS of str1 (0 to i-1) and str2 (0 to j-1)
   for (int i=0; i<=m; i++) {
      for (int j=0; j<=n; j++) {
         if (i == 0 || j == 0)
            longSubSeq[i][j] = 0;
         else if (str1[i-1] == str2[j-1])
            longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
         else
            longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
      }
   }
   return longSubSeq[m][n];
}

int main() {
   string str1 = "AGGTAB";
   string str2 = "GXTXAYB";

   cout << "Length of Longest Common Subsequence is: " <<  longestComSs( str1, str2);
}

ผลลัพธ์

Length of Longest Common Subsequence is: 4