lis.java

public static int LIS(int[] arr) {

        int[] P = new int[arr.length];
        int[] M = new int[arr.length + 1];
        int L = 0;
        int newL = 0;
        
        M[1] = 0;

        for (int i = 0; i < arr.length; i++) {
            int lo = 1;
            int hi = L;

            if (arr[M[1]] >= arr[i]) {
                newL = 1;
            } else { 
                while (lo <= hi) {
                    int mid = (int) Math.ceil(lo + (hi - lo) / 2);
                    if (arr[M[mid]] < arr[i]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;                    
                    }
                }
                newL = lo;
            }
                
            P[i] = M[newL - 1];
            M[newL] = i;

            if (newL > L) {
                L = newL;
            }
        }
        
        int[] res = new int[L];
        int k = M[L];

        for (int i = L - 1; i >= 0; i--) {
            res[i] = arr[k];
            k = P[k];          
        }
        
        return L;

    }