动态规划+二分查找，状态转移公式跟普通的有所不同，用tail数组维护当前最长的公共子序列，如果arr[i]>当前tail[len-1],则tail[len++]=arr[i],dp[i]=len; 如果不成立，则通过二分查找到最小的大于等于arr[i]的位置，插入arr[i]（这样才可以保证后面的序列尽可能长），此时注意更新dp[i]为index+1，而不是len。最后通过逆向遍历的方式就可以找到符合题意的最长上升子序列 

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
//     class node{
//         int cnt=0;
//         List<Integer> record=new ArrayList<>();
//     }
    public int[] LIS (int[] arr) {
        // write code here
        int n=arr.length;
        if(n<=1){
            return arr;
        }
        int []tail=new int[n];
        int []dp=new int[n];
        dp[0]=1;
        tail[0]=arr[0];   //初始化
         int len=1;
        for(int i=1;i<n;i++){
            if(arr[i]>tail[len-1]){
                tail[len++]=arr[i];
                dp[i]=len;
            }
            else {
                int index=findIndex(tail,len,arr[i]);
                tail[index]=arr[i];
//                 len=index+1;
                dp[i]=index+1;
            }
            
        }
        int []res=new int[len];
        for(int i=n-1;i>=0;i--){
            if(len==dp[i])
                res[--len]=arr[i];
        }
//         for(int i:dp){
//             System.out.print(i+" ");
//         }
//         System.out.println();
//         for(int i:tail){
//             System.out.print(i+" ");
//         }
        
        return res;
    
    }
    public int findIndex(int[] arr,int length,int val){
        int i=0,j=length-1;
        while(i<j){
            int mid=(i+j)/2;
            if(val<=arr[mid]){
                j=mid;
            }
            else{
                i=mid+1;
            }
        }
        return i;
        
    }
}