题解 | #最长递增子序列#

#include<bits/stdc++.h>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int n;
    cin>>n;
    int *arr=new int[n];
    //申请一个ends数组ends[b]==c的含义是长度为b+1的所有子序列中结尾最小的数时c
    //再申请一个变量right=0,代表ends数组的有效区域,0..right是有效区域
    //再申请一个动态数组dp，dp[i]的含义为以arr[i]结尾的情况下arr[0..i]的最长递增子序列的大小
    int ends[n],right=0,dp[n];
    dp[0]=1;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    ends[0]=arr[0];//所有长度为1的递增子序列中结尾数最小的是arr[0];
    //填写dp数组
    for(int i=1;i<n;i++){
        //二分查找ends数组中大于等于ar[i]的最左边的数
        int l=0,r=right;
        while(l<=r){
            int mid=(l+r)/2;
            if(ends[mid]>=arr[i]){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        //更新right的范围
        right=max(right,l);
        dp[i]=l+1;
        ends[l]=arr[i];
    }
    //dp数组填写完毕
    //遍历dp数组找到最大且字典序最小的的位置和值
    int Max=dp[0],pos=0;
    int mindata=arr[0];
    for(int i=1;i<n;i++){
        if(dp[i]>Max){
            Max=dp[i];
            pos=i;
            mindata=arr[i];
        }
        else if(dp[i]==Max){
            if(arr[i]<mindata){
                pos=i;
                mindata=arr[i];
            }
        }
    }
    int temp=Max;
    //找到dp数组中最大值和其位置后
    int res[Max];
    res[--Max]=arr[pos];
    //从pos往左找dp[i]==Max&&arr[i]<arr[pos]且最小的
    for(int i=1;i<=temp;i++){
        int min=-1,ans=-1;//值和位置
        for(int j=pos-1;j>=0;j--){
            if(dp[j]==Max&&arr[j]<arr[pos]){
                //找这些符合条件中字典序最小的
                if(min==-1){
                    min=arr[j];
                    ans=j;
                }
                    
                else{
                    if(arr[j]<min){
                        min=arr[j];
                        ans=j;
                    }
                } 
            }
        }
        res[--Max]=min;
        pos=ans;
    }
    for(int i=0;i<temp;i++)
        cout<<res[i]<<" ";
    return 0;
}