O(nlogn)的n个数组成的序列的最长单调递增子序列

    public class F {
    	// 最长递增子序列 O(nlogn)
    	public static int findLongest(int[] arr, int n) {
    		// write code here
    		int[] arrB = new int[n];
    		arrB[0] = arr[0];
    		int end = 0;
    		int index = 0;// 标记
    		for (int i = 0; i < n; i++) {
    			// 当前数比arrB最后一个数要大，添加到arrB
    			if (arr[i] > arrB[end]) {
    				arrB[++end] = arr[i];
    				System.out.print(arr[i - 1] + " ");// 打印前几个递增序列
    				index = i; // 记录位置
    			}
    			// 找到第一个比当前数大的替换
    			else {
    				int pos = findInsertPos(arrB, arr[i], 0, end);
    				arrB[pos] = arr[i];
    			}
    		}
    		System.out.println(arr[index]);// 打印递增序列中最后一个元素
    		return end + 1;
    	}
    
    	// 利用二分查找 确定第一个比它大的元素
    	public static int findInsertPos(int[] arrB, int num, int start, int end) {
    		while (start < end) {
    			int mid = start + (end - start) / 2;
    			if (arrB[mid] < num) {
    				start = mid + 1;
    			} else if (arrB[mid] > num) {
    				end = mid;
    			} else {
    				return mid;
    			}
    		}
    		return start;
    	}
    
    	public static void main(String[] args) {
    
    		Scanner scanner = new Scanner(System.in);
    
    		System.out.println("Please enter the sequence length:");
    		int N = scanner.nextInt();
    		int[] A = new int[N];
    
    		System.out.println("Please enter a number sequence:");
    		for (int i = 0; i < N; i++) {
    			A[i] = scanner.nextInt();
    		}
    		System.out.println("Result:");
    		System.out.println("	Length of LCS is " + findLongest(A, N));
    	}
    
    }

    Please enter the sequence length:
    7
    Please enter a number sequence:
    1 2 6 5 4 3 8 
    Result:
    1 2 3 8
    	Length of LCS is 4