算法实践--最长递增子序列(Longest Increasing Subsquence)

什么是最长递增子序列(Longest Increasing Subsquence)

对于一个序列{3, 2, 6, 4, 5, 1}，它包含很多递增子序列{3, 6}, {2,6}, {2, 4, 5}, {1}

其中最长的递增子序列是{2, 4, 5}

问题：对于长度为N的矢量D，如何找到它的最长递增子序列

一个简单的算法

for (i=N; i>0; --i) {. 找到所有长度为i的子序列;   //复杂度为(N!)/(i!)(N-i)!    O(exp(N))

   . 判断是否其中有一个为递增子序列
}

动态规划算法

基本思想：将一个复杂问题，分解为更小的子问题

首先定义LIS[i]，表示以D[i]结尾的最长子序列

对于矢量D = {, , , , , }；

LIS[]:

LIS[]:

LIS[]:  ,

LIS[]:  ,

LIS[]:  ,,

LIS[]:

给出递推公式

LIS[0] = D[0]

LIS[i] = MAX(LIS[j] | j <i, D[j] <D[i]) + "D[i]"

解释：

当我们求LIS[i]时，对于任意j<i，LIS[j]都已知

在所有已知的LIS中，找出结尾的元素值小于D[i]，长度最长的一个

然后在后面加上D[i]元素，即为LIS[i]

示例C++代码

using namespace std;

void prt(vector<int>& arr, string msg = "") {

    cout << msg << " ";

    for  (auto i: arr) {

        cout << i << " ";

    }

    cout << endl;

}

void calc_LIS(vector<int>& D) {

    vector< vector<int> > L(D.size());  // The longest increasing subsequence ends with D[i]

   L[].push_back(D[]);

    for (int i=; i<D.size(); i++) {

        for(int j=; j<i; j++) {

            if ( (D[j] < D[i]) && ( L[i].size() < L[j].size() ) ) {

                L[i] = L[j];

            }

        }

      L[i].push_back(D[i]);

    }

    for (auto x: L) {

        prt(x);

    }

}

int main() {

    int a[] = {, , , , , };

    vector<int> arr(a, a + sizeof(a)/sizeof(a[]));

    prt(arr, "Data In:");

    calc_LIS(arr);

    return ;

}

复杂度分析

时间复杂度是O(N^2)

动态规范的基本思想是以一定的空间开销，显著缩短时间开销

秒客网