C++计算整数序列的最长递增子序列的长度

喜欢ヅ旅行 2022-07-14 14:44 146阅读 0赞

> Talk is cheap, show me the code.

给定一个整数序列，计算其中的最长递增子序列的长度，这是一个典型的动态规划的算法。

比如8个整数的序列 186 186 150 200 160 130 197 200，最长递增子序列是 150 160 197 200, 长度为4。

想要解决此问题，可以把这个大问题分解为小问题，依次考虑每个数，计算出包含该数数和该数之前的所有数的最长递增子序列的长度，计算出的长度值作为该数的对应值记录下来，最后可以得到这8个数对应的长度值序列，也是8个数，找到这8个数中的最大值就是所有书的最长递增子序列的长度。

或者也可以这样想，想要计算8个数的最长递增子序列的长度有难度，不如先考虑最简单的情况。只有一个数的时候，最长递增子序列长度就是1；当有两个数时，只考虑第一个数和它以前的数的最长递增子序列就是1，考虑第二个数时只需要找到它之前的所有数中比第二个数小的所有数中最长递增子序列的长度最大值然后加一 ，就是第二个数的长度。

下面给出实现代码:

#include <iostream>
    #include <vector>
    #include <iterator>
    using namespace std;
    
    int findLoogestIncreaseSeq(vector<int> &vect)
    {
        int len = 0;
        int *count = new int[vect.size()];
        for (int i = 0; i < vect.size(); i++)
            count[i] = 1;
        for (int i = 0; i < vect.size(); i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (vect[j] < vect[i] && count[j] >= count[i])
                {
                    count[i] = count[j] + 1;
                }
            }
            if (count[i] > len)
                len = count[i];
        }
        delete [] count;
        return len;
    }
    
    int main()
    {
        vector<int> vect;
        int temp;
        while (cin >> temp)
        {
            vect.push_back(temp);
        }
        cout << findLoogestIncreaseSeq(vect) << endl;
    
        return 0;
    }