题目描述
给定数组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;
}
