动静布局求序列的最长递增子序列，c++实现

形容

求序列的最长递增子序列
问题分析

  1. 划分子问题

    1. 只有一个序列的时候，就是序列自身，且长度为1
    2. 序列长度大于2的时候，用L[n]数组寄存每个子问题的最长长度，
    3. 每i个序列地位的解决，都以其前i-1个曾经找到的以后最长比拟最初一位是否合乎递增
    4. 合乎，并且其长度L[i-1]+1大于子问题目前的最大长度，则长度L[i-1]+1，L[i] = L[i-1]+1, 应用arri寄存每一个子问题的最长序列

  2. 递推公式

    1. 长度为1时，L(1) = 1
    2. 长度大于等于2时，L(i) = max{L(i-1) + 1},即为子问题和以后序列组合的最长子序列
  3. 建表

算法实现

#include<iostream>using namespace std;void handlerSort(int arr[], int n) {    int k, L[n], x[n][n], index, i;    // 初始化，全副初始都为1，且存储自身，相似长度为1时     for (i = 0; i<n; i++) {        L[i] = 1;        x[i][0] = arr[i];    }    // 从第一个开始解决，，长度大于2时     for (i = 1; i < n; i++) {        int max = 1; // 以后子问题的最大长度初始为1        // 循环解决子问题，后面i-1个子问题和以后序列是否组合成最新的最长子序列         for (int j = i - 1; j >= 0; j--) {            // 每i个序列地位的解决，都以其前i-1个曾经找到的以后最长比拟最初一位是否合乎递增            if (arr[i] > arr[j] && max < L[j]+1) {                // 长度L[i-1]+1，L[i] = L[i-1]+1                max = L[j] + 1;                L[i] = max;                cout<<"此次后果";                for (k = 0; k < L[j]; k++) {                    x[i][k] = x[j][k];                    cout<<x[i][k]<< " ";                }                x[i][k] = arr[i];                cout<<x[i][k]<<endl;            }        }     }    cout<<"后果为"<<endl;    for (index = 0, i = 1; i < n; i++) {        if (L[index] < L[i]) {            index = i;        }    }    cout<<"长度为"<<index<<" "<<L[index]<<endl;     for (i = 0; i < L[index]; i++) {        cout<<x[index][i]<<" ";    }} int main() {    int a[8] = {5, 2, 8, 6, 3, 6, 9, 7};    handlerSort(a, 8);    return 0;}

后果输入


ps：本算法只求一个最长子序列，如果要求全副子序列，须要把后果存储改为寄存数组指针，而后比拟每一个数组指针，从而得出全副后果。