题解 | #Redraiment的走法#

import java.io.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String str = null; while((str = in.readLine()) != null){ int num = Integer.parseInt(str); String[] arr = in.readLine().split(" "); int[] res = new int[num]; for(int i = 0;i < num;i++){ res[i] = Integer.parseInt(arr[i]); } System.out.println(lengthOfLIS(res)); } } public static int lengthOfLIS(int[] arr){ int[] res = new int[arr.length + 1]; int tail = 1; res[0] = Integer.MIN_VALUE; res[1] = arr[0]; for(int i = 1;i < arr.length;i ++){ if(arr[i] > res[tail]){ tail ++; res[tail] = arr[i]; }else { int temp = binarySearch(res,arr[i],0,tail); res[temp] = arr[i]; } } return tail; } public static int binarySearch(int[]arr,int dest,int left,int right){ if(left == right) return right; int mid = (left + right)/2; if(arr[mid] >= dest){ right = mid; }else if(arr[mid] < dest){ left = mid+1; } return binarySearch(arr,dest,left,right); } }