import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    //思路：
    /*
    1.维护一个临时数组tmp,这里面存储当前的最长上升子序列；
    2.遍历arr中的元素，不断的将当前元素加入tmp，或者替换tmp中的元素，使得tmp保持上升；
        2.1 对于arr[i] ，若其大于tmp的最后一个元素，那么直接将其加入到tmp的末尾，
        2.2 对于arr[i]，若其小于tmp的最后一个元素，则在tmp从左到右中找到第一个比奇大的元素并替换他
    3.每次处理完一个arr[i]，都将arr[i]加入到或者替换到tmp的位置记录到pos中，如pos[i]表示arr[i]在tmp中的位置
    4.整过程中，tmp的长度都是不减的，因此，最后tmp的长度就是最长上上升子序列的长度，从tmp的最后一个元素开始向前遍历(s从后往前是为了
    保证，结果是按字典序取最小的要求，这一点你们自己思考吧，不难)，在pos中寻找位置为tmp中对应位置的pos[i]，将arr[i]记录到结果数组中即可。
    */
    public int[] LIS (int[] arr) {
        if(arr == null || arr.length == 0) return arr ;
        //tmp[i]表示 当前最长上升子序列 i位置的 元素
        int tmp[] = new int[arr.length] ;
        //pos[i]表示 将arr[i]加入当前最长上升子序列中 时arr[i]应该在序列中的 位置
        int pos[] =  new int[arr.length] ;
        tmp[0] = arr[0] ;
        pos[0] = 0 ;
        int tmpIndex = 0 ;//当前最长上升子序列的最后一元素的 位置
        for(int i = 1 ; i < arr.length ; i ++) {
            if(arr[i] > tmp[tmpIndex]) {
                tmp[++ tmpIndex] = arr[i] ;
                pos[i] = tmpIndex ;
            } else if(arr[i] == tmp[tmpIndex]) {
                pos[i] = tmpIndex ;
            } else {
                //二分查找位置
                int findIdx = findPos(tmp , tmpIndex , arr[i]) ;
                tmp[findIdx] = arr[i] ;
                pos[i] = findIdx ;
            }
        }
        int res[] = new int[tmpIndex + 1] ;
        for(int j = tmpIndex , i = arr.length - 1 ; j >= 0 ; i --) { 
            if(pos[i] == j) {
                res[j --] = arr[i] ;
            }
        }
        return res ;
        
    }
    //在tmp中 查找第一个比target大的数
    public int findPos(int tmp[] , int end , int target) {
        int i = 0 ;
        int j = end ;
        while(i <= j) {
            int mid = i + (j - i) / 2 ;
            if(target > tmp[mid]) {
                i = mid + 1 ;
            } else {
                j = mid - 1 ;
            }
        }
        return i ;
    }
}