- LIS
- import java.util.*;
- public class Main1{
- public static int findLongest(int[] s, int n) {
- int []dp= new int[10001];
- dp[0]=s[0];
- int len=1;
- for(int i=1;i<n;i++){
- int left= 0,right=len-1,mid;
- if(dp[len-1]<s[i])
- dp[len++]=s[i];
- else{
- right=len-1;
- while(left<=right){
- mid= (left+right)/2;
- if(dp[mid]<s[i])
- left=mid+1;
- else
- right=mid-1;
- }
- dp[left]=s[i];
- }
- }
- return len;
- }
- public static void main(String[] args) {
- Scanner sc=new Scanner(System.in);
- while(sc.hasNext()){
- int n=sc.nextInt();
- int[] A=new int[n];
- for(int i=0; i<n; i++){
- A[i]=sc.nextInt();
- }
- int res=findLongest(A, n);
- // int res=n-max+1;
- System.out.println(res);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2980946.html