题解

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
       int[] ans = new int[arr.length];
       int size = 0;
       int[] position = new int[arr.length];
       int[] pre = new int[arr.length];
       for(int i = 0;i < arr.length; i++) {
           int low = 0, high = size - 1;
           while(low <= high) {
               int mid = (low+high) / 2;
               int value = ans[mid];
               if(value >= arr[i]) {
                   high =  mid - 1;
               } else {
                   low = mid +1;
               }
           }
           if(low == size){
               ans[size++] = arr[i];
           } else {
               ans[low] = arr[i];
           }
           position[low] = i;
           if(low == 0) {
               pre[i] = -1;
           } else {
               pre[i] = position[low-1];
           }
       }
        int[] result = new int[size];
        int p = position[size-1];
        int cnt = size - 1;
        while(p != -1) {
            result[cnt--] = arr[p];
            p = pre[p];
        }
        return result;
    }
}