#include<bits/stdc++.h>
using namespace std;
int getIndex(vector<int>& v,int x)
{
    int res = -1;
    int left = 0;
    int right = v.size()-1;
    while(left<=right)
    {
        int mid = (left+right)>>1;
        if(v[mid]>=x)
        {
            res = mid;
            right = mid-1;
        }
        else left = mid + 1;
    }
    return res;
}
vector<int> getLIS(vector<int>&v,vector<int>& dp)
{
    // maxLen
    int maxLen = 0;
    int index = 0;
    for(int i=0;i<dp.size();++i)
    {
        // 字典序的话，这里要取>=
        if(dp[i]>=maxLen)
        {
            maxLen = dp[i];
            index = i;
        }
    }
    //cout<<"maxlen "<<maxLen<<" index"<<index<<endl;
    vector<int>ans(maxLen);
    ans[--maxLen] = v[index];
    vector<int>temp;
    for(int i=index;i>=0;--i)
    {
        if(v[i]<v[index] && dp[i]==dp[index]-1)
        {
            ans[--maxLen] = v[i];
            index = i;
        }
    }
    return ans;
}

int main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i) cin>>v[i];
    vector<int>record;
    // dp[i] 以v[i]结尾的序列的最大长度
    vector<int>dp(n);
    dp[0] = 1;
    record.push_back(v[0]);
    //int use = -1;
    for(int i=1;i<n;++i)
    {
        int l = getIndex(record,v[i]);
        if(l != -1)
        {
            record[l] = v[i];
            dp[i] = l + 1;
        }

        else
        {
            record.push_back(v[i]);
            dp[i] = record.size();
        }
    }
    //for(int i:dp)
    //    cout<<i<<endl;
    vector<int> ans = getLIS(v,dp);
    for(int i : ans)
        cout<<i<<" ";

}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, l=0, k;
    scanf("%d", &n);
    int a[n], b[n], dp[n]={0};
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        int t = lower_bound(b, b+l, a[i]) - b;
        if(t == l){
            b[l++] = a[i];
            dp[i] = l;
            k = i;
        }else{
            b[t] = a[i];
            dp[i] = t+1;
            if(dp[i] == l)
                k = i;
        }
    }
    int r[l], m=l;
    r[--l] = a[k];
    for(int i=k;i>=0;i--){
        if(a[i]<a[k] && dp[i]==dp[k]-1){
            r[--l] = a[i];
            k = i;
        }
    }
    for(int i=0;i<m;i++)
        printf("%d ", r[i]);
}

import java.util.*;
import java.io.*;
//这里用到了java自带的二分查找法，当然可以自己写，int binarySearch(int []arr,int s, int e, int key )。左闭右开。该方法要求数组非严格单调增。
//该方法自动查找到数组中第一个等于key的值的索引（假设arr中有key），返回该索引；如果没有则会找到第一个大于key的值的索引x。并返回: - x - 1。
//若数组中元素均小于key则返回: - len - 1。也就是可以利用返回值找到一个大于或等于key的值的索引。
//最好自己画图看看，很容易看出来。给一个设计好的测试用例 { 9,10,11,12, 8, 4, 15, -5, -4, -3, 7 }。 
public class Main{
    public static  void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = Integer.parseInt(s[i]);
        }
        lengthOfLIS(arr);
    }
    
    public static int lengthOfLIS(int[] nums){
		// 1.minTail[i]用来记录所有长度为i+1的递增序列中，末尾的最小值。可以用反正法证明minTail数组必然是一个单调递增数组。下面关键步骤是通过遍历nums数组逐渐的得到minTail
        // 2.dp[i] 记录以数组nums中第i个数字结尾的LIS的长度。
        // 3.通多上面两个数组求出最小LIS
		int[] minTail = new int[nums.length];//minTail数组真实长度就是LIS长度，不确定，所以创建了一个和nums等长的数组，初始值均为0。
		int[] dp = new int[nums.length];//数组dp长度等于nums长度
		int len = 0;//表示minTail目前用到的长度
        
		for (int l = 0; l < nums.length; l++){// 随着数组的遍历不断地跟新minTail
			// 搜索第一个大于nums[l]的数的位置。
			int i = Arrays.binarySearch(minTail, 0, len, nums[l]);
            while(i>=0){//若查找到minTail中包含nums[l],接着二分查找直到找到第一个大于nums[l]的数
                i = Arrays.binarySearch(minTail, i+1, len, nums[l]);
            }
			i = -i - 1;//得到大于nums[l]的第一个值的索引
            
			// 已有序列都小于num
			if (i == len){
				len++;
			}
			// 替换掉第一个大于或等于nums[l]的数,也就是说长为i+1的递增子序列最小值可以是更小的nums[l]。如果数组中没有比num大的数则num添加到末尾。
			minTail[i] = nums[l];
			dp[l] = i + 1;
		}

		// 下面代码用来找到按照字母表排序最小的最长递增子序列
		int[] res = new int[len];
		int index = res.length - 1;
		int next = Integer.MAX_VALUE;
		for (int k = nums.length - 1; k >= 0; k--){
			if (nums[k] <= next && dp[k] == index + 1){//满足该条件求得的序列就是目标LIS。假设已知LIS最后一个数字（其实就是minTail中最后一个非0值
                //通过该判断求LIS前一个数值？（首先该条件为nums[k]是LIS倒数第二个数值的充分条件，但还需证明由该条件得到的LIS按字典排序最小）。假设除了k满足该条件，
                //还有i，j...满足，那么i，j...不可能在k之后（因为倒着遍历nums），所以推出num[i,j,...]必然大于nums[k]。绝不可能小于或者等于，否则可以推出dp[k]==index+2
				res[index] = nums[k];
				next = res[index];
				index--;
			}
		}
        StringBuilder sb = new StringBuilder();
		for (int val : res)
            sb.append(val).append(" ");
		System.out.println(sb.toString());

		return len;
	}
}

#include <vector>

using namespace std;

int maxNumber(int a, int b);

vector<int> getDP(vector<int> arr);

vector<int> getList(vector<int> arr, vector<int> dp);

int main()

{

    int CntOfNumbers = 0;

    int numberOfArray = 0;

    vector<int> array;

    vector<int> result;

    vector<int> dp;

    //输入数组大小

    cin >> CntOfNumbers;

    //数组元素

    for(int i = 0; i < CntOfNumbers;i++)

    {

        cin >> numberOfArray;

        array.push_back(numberOfArray);

    }

    //dp[i]表示遍历到arr[i]时，arr[0...i]组成的最长子序列长度

    dp = getDP(array);

    result = getList(array, dp);

    int length = result.size();

    for(int i = 0; i < length; i++)

    {

        cout << result[i] << " ";

    }

    return 0;

}

int maxNumber(int a, int b)

{

    return a > b ? a : b;

}

vector<int> getDP(vector<int> arr)

{

    int length = arr.size();

    vector<int> dp(length, 0);

    vector<int> end(length, 0);

    //有效区的右边界会更新

    int right = 0;

    int l = 0, m = 0, r = 0;

    end[0] = arr[0];

    dp[0] = 1;

    //开始对后面的数字用二分法更新end数组和dp数组

    for(int i = 1; i < length; i++)

    {

        l = 0;

        r = right;

        //找到end中最左边大于或等于arr[i]的位置，或者直接大于end最右边的数,l走到了right+1处

        while(l <= r)

        {

            m = (l + r)/2;;

            if(arr[i] > end[m])

                l = m + 1;

            else

                r = m - 1;

        }

        //扩大有效区

        right = maxNumber(right, l);

        //更新数组

        end[l] = arr[i];

        dp[i] = l + 1;

    }

    return dp;

}

vector<int> getList(vector<int> arr, vector<int> dp)

{

    int length = arr.size();

    //最长子序列的长度和对应的下标

    int len = 0;

    int index = 0;

    for(int i = 0; i < length; i++)

    {

        //滑到最右边那个最大的dp[i]和下标

//因为当dp相同时，最右边那个数最小，所以接下来第一个找到符合要求的数就可以直接存入数组中

        if(dp[i] >= len)

        {

            len = dp[i];

            index = i;

        }

    }

    //开始寻找最小值的最长子序列

    vector<int> list(len, 0);

    //先放置最后那个数

    list[--len] = arr[index];

    //从后往前遍历

    for(int i = index - 1; i >= 0; i--)

    {

        //要满足两个条件

        if(arr[i] < arr[index] && dp[i] == (dp[index] - 1))

        {

            list[--len] = arr[i];

            index = i;

        }

    }

    return list;

}

//二分查找+贪心
#include "bits/stdc++.h"
using namespace std;

int midsearch(int target,vector<int>& arr1,vector<int>& arr){
    //arr1中第一个对应到arr中的值大于等于target的下标
    int l=0,r=arr1.size();
    int mid;
    while(l<r){
        mid=(l+r)>>1;
        if(arr[arr1[mid]]==target) {
            while(mid-1>=0&&arr[arr1[mid-1]]==target)
                mid--;
            return mid;
        }
        else if(arr[arr1[mid]]>target) r=mid;
        else if(arr[arr1[mid]]<target) l=mid+1;
    }
    return l;
}    

int main()
{
    //贪心+二分查找可以求出最大递增子序列长度
    //怎么得到最大递增子序列？
    //arr1[i]表示递增长度最大长度为i时，使第i个值最小的arr的下标
    //dp[i]表示arr[i]作为其中一个值时，它的的前一个值的下标
    int len;cin>>len;
    vector<int> arr(len);
    for(int i=0;i<len;i++) cin>>arr[i];
    vector<int> dp(len,-1);
    vector<int> arr1;
    arr1.push_back(0);
    for(int i=1;i<len;i++){
        int target=arr[i];
        if(target>arr[arr1.back()]){
            dp[i]=arr1.back();
            arr1.push_back(i);
        }
        else{
            int t=midsearch(target, arr1,arr);
            arr1[t]=i;
            if(t>0) dp[i]=arr1[t-1];
        }
    }
    int len1=arr1.size();
    vector<int> ret(len1,0);
    ret[len1-1]=arr[arr1.back()];
    int j=len1-2;
    int last=dp[arr1.back()];
    //for(int i=0;i<len;i++)cout<<dp[i];
    while(j>=0){
        ret[j]=arr[last];
        j--;
        last=dp[last];
    }
    for(int i=0;i<len1;i++){
        cout<<ret[i]<<' ';
    }    
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

  public static void longestIncreasingSequence(int[] num) {
    int[] arr = new int[num.length];
    int[] dp = new int[num.length];
    int sum = 0;
    int idx;
    for (int i = 0; i < num.length; ++i) {
      idx = Arrays.binarySearch(arr, 0, sum, num[i]);
      while (idx > 0) {
        idx = Arrays.binarySearch(arr, idx + 1, sum, num[i]);
      }
      if (sum == -idx - 1) {
        sum++;
      }
      arr[-idx - 1] = num[i];
      dp[i] = -idx;
    }

    int[] res = new int[sum];
    int index = res.length - 1;
    int next = Integer.MAX_VALUE;
    for (int k = num.length - 1; k >= 0; --k) {
      if (num[k] <= next && dp[k] == index + 1) {
        res[index] = num[k];
        next = res[index];
        if ((--index) < 0) {
          break;
        }
      }
    }
    StringBuilder builder = new StringBuilder("");
    for (int re : res) {
      builder.append(re).append(" ");
    }
    System.out.println(builder.toString());
  }

  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bufferedReader.readLine());
    String[] str = bufferedReader.readLine().split(" ");
    int[] num = new int[n];
    for (int i = 0; i < n; ++i) {
      num[i] = Integer.parseInt(str[i]);
    }
    longestIncreasingSequence(num);
  }
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(in.readLine());
        String[] t = in.readLine().split(" ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(t[i]);

        int[] q = new int[n + 10], f = new int[n + 10];
        int len = 0, idx = 0;
        for (int i = 0; i < n; i++) {
            int l = 0, r = len;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] < nums[i]) l = mid;
                else r = mid - 1;
            }
            q[l + 1] = nums[i];
            f[i] = Math.max(f[i], l + 1);
            if (f[i] >= len) {
                len = f[i];
                idx = i;
            }
        }
        int[] ans = new int[len];
        for (int i = idx; i >= 0; i--) {
            if (f[i] == len) ans[--len] = nums[i];
        }
        for (int i = 0; i < ans.length; i++) out.write(ans[i] + " ");
        out.flush();
    }
}

def solution(nums):
    stack = []
    pre_idx = [-1] * len(nums)
    for idx, num in enumerate(nums):
        if not stack&nbs***bsp;num > nums[stack[-1]]:
            stack.append(idx)
            pre_idx[idx] = stack[-2] if len(stack) > 1 else -1
        else:
            l, r = 0, len(stack) - 1
            loc = r
            while l <= r:
                mid = (l + r) // 2
                if nums[stack[mid]] >= num:
                    loc = mid
                    r = mid - 1
                else:
                    l = mid + 1
            stack[loc] = idx
            pre_idx[idx] = stack[loc - 1] if loc >0 else -1
    idx = stack[-1]
    res = []
    while idx != -1:
        res = [str(nums[idx])] + res
        idx = pre_idx[idx]
    return res
#     return [str(item) for item in val_idx]
n = map(int, input().strip())
array = list(map(int, input().strip().split()))
# print(array)
res = solution(array)
print(' '.join(res))

C++解法，动态规划+贪心法

思路分析：

#include <bits/stdc++.h>
using namespace std;

// 得到dp数组
static void getdp(vector<int> &v, vector<int> &dp, int &maxlen){
    int sz = v.size();
    vector<int> ends(sz, 0);
    dp[0] = 1;
    ends[0] = v[0];
    int right = 1;
    for(int i=1;i<sz;i++){
        int fleft = 0;
        int fright = right;
        while(fleft < fright){
            int mid = fleft + ((fright-fleft)>>1);
            if(ends[mid] < v[i])
                fleft = mid + 1;
            else
                fright = mid;
        }
        dp[i] = fleft + 1;
        ends[fleft] = v[i];
        if(fright == right)
            ++right;
    }
    maxlen = right;
    return ;
}

static void getminseq(vector<int> &v, vector<int> &res, vector<int> &dp, int maxlen){
    int find = maxlen;
    int sz = v.size();
    vector<int> limit(maxlen+1, 0);
    int pos = maxlen;
    // 构造limit，查找的右边界
    for(int i=sz-1;i>=0;--i){
        if(dp[i] == find){
            limit[pos--] = i;
            find--;
        }
    }

    pos = 0;
    int left = 0, right = 0, minpos=0, minvalue=0;
    for(int target=1;target<=maxlen;target++){
        minvalue=INT_MAX;
        left = minpos;  // 上一次的最优解位置作为左边界
        right=limit[target];   // limit作为右边界
        for(int k=left;k<=right;k++){     // 范围内查找最小元素
            if(dp[k] == target){
                if(v[k] < minvalue){
                    minvalue = v[k];
                    minpos = k;
                }
            }
        }
        res[pos++] = minvalue;
    }
    return;
}

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    vector<int> dp(n, 0);
    int maxlen;
    getdp(v, dp, maxlen);
    vector<int> res(maxlen, 0);
    getminseq(v, res, dp, maxlen);
    for(int num : res)
        cout<<num<<" ";
    return 0;
}

#include <iostream>
using namespace std;
#define N 100000
int arr[N];
int dp[N];
int my_ends[N];
int record[N];
int main()
{
    int n;
    cin>>n;
    for(int indx=0;indx<n;++indx)
    {
        cin>>arr[indx];
    }
    
    // dp process
    dp[0]=1;
    int right=0;
    my_ends[0]=arr[0];
    int l=0;
    int r=0;
    int m=0;
   
    int dp_max_rec=1;
    int dp_max_indx=0;
    for(int i=1;i<n;++i)
    {   
        l=0;
        r=right;
        while(l<=r)
        {
            m=(l+r)/2;
			if(arr[i]>my_ends[m])
				l=m+1;
			else
				r=m-1;
            
        }
		dp[i]=l+1;
		my_ends[l]=arr[i];
		if(l>right)
			right=l;
		if(dp[i]>=dp_max_rec)
		{
			dp_max_rec=dp[i];
			dp_max_indx=i;
		}
    }
    record[dp_max_rec-1]=dp_max_indx;
    int cur=dp_max_rec-1;
    for(int indx=dp_max_indx-1;indx>=0;--indx)
    {   
        if(cur<=0)
        {
            break;
        }
        if(dp[indx]==dp[record[cur]]-1&&arr[indx]<arr[record[cur]])
        {
            --cur;
            record[cur]=indx;
            continue;
        }
        if(dp[indx]==dp[record[cur]]&&arr[indx]<arr[record[cur]])
        {
            record[cur]=indx;
            continue;
        }
        if(dp[indx]>dp[record[cur]])
        {
            if(arr[indx]<arr[record[dp[indx]-1]])
            {
                cur=dp[indx]-1;
                record[cur]=indx;
                continue;
            }
        }
    }
    for(int indx=0;indx<dp_max_rec;++indx)
    {
        cout<<arr[record[indx]];
        if(indx==dp_max_rec-1)
            cout<<'\n';
        else
            cout<<' ';
    }
    return 0;
}

#include<iostream>
(720)#include<algorithm>
using namespace std;



int *arr;
int *dp;
int *bin;
int *lis;
//二分查找利用bin数组能优化dp数组的计算速度
int BinarySearch(int *bin, int len, int n){
	int left = 1;
	int right = len;
	while (left < right){
		int mid = (left + right) / 2;
		if (bin[mid] > n){
			right = mid;
		}
		else{
			left = mid + 1;
		}
	}
	return right;
}


int getResult1(int n){
	dp[0] = 1;
	bin[1] = arr[0];
	int index = 1;
	for (int i = 1; i < n; i++){
		if (arr[i] > bin[index]){
			bin[++index] = arr[i];

			dp[i] = index;

		}
		else{
			int temp = BinarySearch(bin, index, arr[i]);
			bin[temp] = arr[i];

			dp[i] = temp;
		}
	}
	return index;


}

int main(){
	int n;
	cin >> n;
	arr = new int[n];
	dp = new int[n + 1];
	bin = new int[n + 1];

	for (int i = 0; i < n; i++){
		cin >> arr[i];
	}
    //根据dp数组计算lis数组
	int ans = getResult1(n);
	int length = ans;

	lis = new int[ans];
	int index = 0;
	
	for (int i = n - 1; i >= 0; i--){

		if (dp[i] == ans){
			lis[--ans] = arr[i];
			index = i;
			break;
		}
	}
	index--;
	for (int i = index; i >= 0; i--){
		if (dp[i] == ans){
			lis[--ans] = arr[i];
		
		}
		

	}

	for (int i = 0; i < length; i++){
		cout << lis[i] << endl;
	}

	delete[] arr;
	delete[] dp;
	delete[] bin;
	delete[] lis;

	return 0;
}

//这个本地所有测试样例都可以通过，牛客超时，应该需要用二分
#include<cstdio>
#include<vector>
using namespace std;
vector<int> dp;
vector<int> v;
int choice[100010];
vector<int> maxpath;
int main() {
	int n;
        scanf("%d", &n); 
		dp.resize(n);
		v.resize(n);
		maxpath.clear();
		fill(choice, choice + 100010, -1);
		//choice.resize(n);
		for (int i = 0; i < n; ++i) {
			scanf("%d", &v[i]);
			dp[i] = 1;
		}
		int mmax = 1, mmaxi = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (v[j] < v[i]) {
					if (dp[j] + 1 > dp[i])
					{
						dp[i] = dp[j] + 1;
						choice[i] = j;
					}
					else if (dp[j] + 1 == dp[i]) {
						if (v[choice[i]] >=v[j]) {
							choice[i] = j;
						}
					}
				}
			}
			if (mmax <= dp[i]) {
				mmax = dp[i];
				mmaxi = i;
			}
		}
		while (mmaxi != -1) {
			maxpath.push_back(mmaxi);
			mmaxi = choice[mmaxi];
		}
		int flag = 0;
		for (int i = maxpath.size() - 1; i >= 0; --i) {
			if (flag == 0) {
				printf("%d", v[maxpath[i]]);
				flag = 1;
			}
			else {
				printf(" %d", v[maxpath[i]]);
			}
		}
	return 0;
}