动态规划求序列的最长递增子序列,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:本算法只求一个最长子序列,如果要求全部子序列,需要把结果存储改为存放数组指针,然后比较每一个数组指针,从而得出全部结果。

评论

暂无评论