アルゴリズム_動的計画_最長単調増分サブシーケンス問題(O(nlogn)の時間的複雑さ)

import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr;
    static int[] dp;

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        arr=new int[n];
        dp=new int[n+1];
        for(int i=0;iint flag=1;
        dp[1]=arr[0];
        for(int i=1;iif(arr[i]>dp[flag]){
                dp[++flag]=arr[i];
            }else{
                int index=binarySearch(i,flag);
                dp[index]=arr[i];
            }
        }

        System.out.println(flag);
    }

    static int binarySearch(int i,int flag){
        int high=flag;
        int low=1;
        while(true){
            if(highreturn low;
            }
            if(high==low){
                return high;
            }
            int mid=(high+low)/2;
            if(arr[i]==dp[mid]){
                return mid; 
            }else if(arr[i]1;
            }else{
                low=mid+1;
            }
        }
    }

}