最长递增子序列

    科技2022-07-20  113

    题目描述

    给定数组arr,设长度为n,输出arr的最长递增子序列。(如果有多个答案,请输出其中字典序最小的)

    示例1

    输入

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

    输出

    [1,3,4,8,9]

    示例2

    输入

    [1,2,8,6,4]

    输出

    [1,2,4]

    说明

    其最长递增子序列有3个,(1,2,8)、(1,2,6)、(1,2,4)其中第三个字典序最小,故答案为(1,2,4) #include<iostream> #include<vector> using namespace std; vector<int> getdp1(vector<int>& arr) { // write code here vector<int> dp(arr.size(), 0); for(int i=0;i<arr.size();i++){ dp[i]=1; for(int j =0;j<i;j++){ if(arr[i]>arr[j]){ dp[i] = max(dp[i],dp[j]+1); } } } return dp; } vector<int> getdp2(vector<int> &arr){ vector<int> dp(arr.size(), 0); vector<int> ends(arr.size(), 0); ends[0]=arr[0]; dp[0]=1; int right = 0; int l = 0; int r = 0; int m = 0; for(int i=1; i<arr.size();i++){ l = 0; r = right; while(l<=r){ m = (l+r)/2; if(arr[i]>ends[m]){ l = m+1; }else{ r = m-1; } } right = max(right, l); ends[l]=arr[i]; dp[i]=l+1; } return dp; } vector<int> generateLIS(vector<int> &arr, vector<int> &dp){ int len = 0; int index = 0; for(int i=dp.size()-1;i>=0;i--){ if(dp[i]>len){ len = dp[i]; index = i; } } vector<int>lis(len, 0); lis[--len] = arr[index]; for(int i = index ; i>=0; i--){ if(arr[i]<arr[index] && dp[i]==dp[index]-1){ lis[--len] = arr[i]; index = i; } } return lis; } vector<int> LIS(vector<int>& arr){ if(arr.empty()) return {}; vector<int> dp = getdp2(arr); return generateLIS(arr, dp); } int main(){ vector<int> arr{1,2,8,6,4};//{2,1,5,3,6,4,8,9,7}; vector<int> res = LIS(arr); for(int i=0;i<res.size();i++){ cout<<res[i]<<" "; } cout<<endl; system("pause"); return 0; }

     

    Processed: 0.090, SQL: 8