最長公共子序列（Longest Common Subsequence，LCS）算法是一種用於比較兩個序列的算法，它尋找的是兩個序列中最長的公共子序列。這裡的「序列」可以是各種形式的數據，如字元串、數組、列表等，而「子序列」則是指從原序列中刪除一些元素後，不改變剩餘元素的相對順序得到的序列。LCS算法在多個領域都有套用，例如在軟體版本管理、軟體測試、基因工程、防抄襲系統、程式代碼相似度度量、視頻段匹配等。
LCS算法的基本思想是通過動態規劃來解決問題，其核心在於構建一個表格來保存中間計算結果，避免重複計算。這個表格的每個單元格代表了某個子問題的解，即兩個較短序列的LCS長度。算法從左上角的單元格開始，逐步填寫表格，直到找到完整的LCS或確定其長度。
例如，對於序列X=[A,B,C,B,D,A,B]和Y=[A,B,D,A,B,C,F]，LCS算法可以計算出這兩個序列之間的最長公共子序列的長度。如果序列X和Y的長度分別為m和n，那麼這個算法的時間複雜度通常是O(mn)，其中m和n分別是兩個序列的長度。
此外，LCS算法還有一些變種，如使用遞歸方法解決，但這種方法效率較低，因為需要重複計算許多子問題。動態規劃方法則通過保存中間結果來避免重複計算，從而顯著提高效率。