C++ 最长公共子序列 Sub Sequence

最长公共子序列是一个经典的基础算法问题 在两个序列中 如果序列1中的元素a也存在于序列2，则认为a是1，2的公共元素。 当序列3中的每一个元素都能够满足在不改变次序的情况下依次属于1，2，那么则认为3是1，2的公共子序列。多个公共子序列中，元素最多的即为最长公共子序列。

在学堂在线的算法课程中，有比较详细的课程讲述这个算法的构思。但是没有给出具体的实现，这里来自己实现一下。

首先使用表格模拟排列组合的所有情况: 以{a,b,c,d,e},{a,b,q,c,b}为例:

实际上看到这样的填充，直觉上就应该反应出来，使用二维数组来解决。 其中当 A[i]!=B[j]时，取左方或者上方更大的，而A[i]==B[j]的时候，取T[i-1][j-1] + 1。这里i=0或j=0的时候就不方便了，所以给矩阵默认增加一行 0 行。即

这样的话，无论如何都可以取到左侧和上方的值。而对应的集合数量、i、j分别+1.

#include <iostream>

using namespace std;

inline int larger( int a, int b ){

    return a>b ? a : b;
}

template <typename T>
int subSquence( T* const A, T* const B, int sizeA, int sizeB ){

    sizeA++;sizeB++; // 增加默认0行
    int t[sizeA][sizeB];
    for( int i=0; i<sizeA; i++ ){
        for( int j=0; j<sizeB; j++ ){
            if( i == 0 || j == 0 ){ // 0行 || 0列
                t[i][j] = 0;
            }else if( A[i-1] == B[j-1] ){ // 相等 * size已经+1了
                t[i][j] = t[i-1][j-1] + 1;
            }else{
                t[i][j] = larger( t[i-1][j], t[i][j-1] );
            }
        }
    }
    return t[sizeA-1][sizeB-1];
}



int main(){

    int a[3] = {1,2,5};
    int b[4] = {2,3,4,5};

    cout << subSquence( a , b, 3, 4 ) << endl;
    return 0;
}