关于后端:动态规划求序列的最长递增子序列c实现

动静布局求序列的最长递增子序列，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：本算法只求一个最长子序列，如果要求全副子序列，须要把后果存储改为寄存数组指针，而后比拟每一个数组指针，从而得出全副后果。