动态规划--最长递增子序列

待我称王封你为后i 2022-08-18 02:17 168阅读 0赞

对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A\[Ui\] < A\[Ui+1\]。

给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。

测试样例：

[2,1,4,3,1,5,6],7

返回：4

代码实现：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    /*
    函数功能：
       dp[i]代表arr[i]处的最长子序列
       利用数组end[],每次在end数组里面进行二分查找
       把时间复杂度降为O(N*logN)
    参数解释：
       n：代表arr数组中数的个数
    */
    
    int getdp(const int arr[], const int n, int dp[])
    {
        if (arr == NULL || n <= 0)
        {
            return 1;
        }
    
        int* ends = new int[n];
        int right = 0,i = 0;
    
        /* l,r,mid代表ends数组二分查找时候的左右边界,和中间值 */
        int l = 0, r = 0, m = 0;
    
        ends[0] = arr[0];
        dp[0] = 1;
    
        for(i = 1; i < n; i++)
        {
            l = 0;
            r = right;
    
            /* 二分查找 */
            while(l <= r)
            {
                m = (l + r) / 2;
                if(arr[i] > ends[m])
                {
                    l = m + 1;
                }
                else
                {
                    r = m - 1;
                }
            }
    
            /* arrp[i]在ends数组中如果找到，就替换掉该值
               如果没有找到。就在ends数组后面加一个值 */
            right = max(right,l);
            ends[l] = arr[i];
    
            dp[i] = l + 1;
        }
    
        delete[] ends;
        return 0;
    }
    
    /* 根据dp数组找出最长的递增字串，放入incList中 */
    void generateLIS(const int arr[],const int n, const int dp[],vector<int> &incList)
    {
        int len = 0, index = 0, i = 0;
    
        /* 找出dp数组中最大的值，也就是最长子序列 */
        for(i = 0; i < n; i++)
        {
            if(dp[i] > len)
            {
                len = dp[i];
                index = i;
            }
        }
    
        /* 更改incList的大小 */
        incList.resize(len);
        incList[--len] = arr[index];
    
        for(i = index; i >= 0; i--)
        {
            if (arr[i] < arr[index] && dp[i] == dp[index] - 1)
            {
                incList[--len] = arr[i];
                index = i;
            }
        }
    }
    int main()
    {
        int arrData [10] = {203,39,186,207,83,80,89,237,247,7};
        int dp[10] = {0};
        vector<int> vecList;
        int i = 0;
    
        getdp(arrData,10,dp);
        generateLIS(arrData,10,dp,vecList);
    
        for(i = 0; i < vecList.size(); i++)
        {
            cout << vecList[i] << " ";
        }
        cout << endl;
    }