数据结构：LISS最长递增子序列动态规划DP

╰+攻爆jí腚メ 2022-05-31 12:24 220阅读 0赞

# 问题是什么 #

这道题是求最长的递增序列，同样也是一个十分经典的动态规划DP解决的做法。

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    const int SIZE = 8;
    int a[SIZE] = { 35, 36, 39, 3, 15, 27, 6, 42 };
    int result[SIZE] = { 0 };
    unsigned int LISS()
    {
        //变长数组参数，用于记录当前各元素作为最大元素的最长递增序列长度
        int liss[SIZE];
        //前驱元素数组，记录当前以该元素作为最大元素的递增序列中该元素的前驱节点，用于打印序列用
        int pre[SIZE];
        for (int i = 0; i < SIZE; ++i)
        {
            liss[i] = 1;
            pre[i] = i;
        }
    
        int max = 1, index = 0;;
        for (int i = 1;i < SIZE; ++i)
        {
            //找到以array[i]为最末元素的最长递增子序列
            for (int j = 0; j < i; ++j)
            {
                //如果要求非递减子序列只需将array[j] < array[i]改成<=，
                //如果要求递减子序列只需改为>
                if (a[j] < a[i] && liss[j] + 1> liss[i])
                {
                    liss[i] = liss[j] + 1;
                    pre[i] = j;
                }
            }
            //得到当前最长递增子序列的长度，以及该子序列的最末元素的位置
            if (max < liss[i])
            {
                max = liss[i];
                index = i;
            }
        }
    
        //输出序列
        int i = max - 1;
        while (pre[index] != index)
        {
            result[i--] = a[index];
            index = pre[index];
        }
        result[i] = a[index];
        cout << "最长递增子序列长度是：" << max << endl;
        for (int i = 0; i < max; i++)
        {
            cout << result[i] << " ";
        }
        return max;
    }
    
    int main()
    {
        LISS();
        system("pause");
        return 0;
    }