バイナリ検索を使用して最長増加するサブシーケンス

Question

バイナリ検索を使用して最長増加サブシーケンスを実装しようとしています。私はアルゴリズムをコーディングしてテストケースが満足していますが、コードを提出すると、次のリストのようないくつかのテストケースでは失敗しています。

29471 5242 21175 28931 2889 7275 19159 21773 1325 6901、答えは4でなければなりませんが、私は5.Belowを取得しています、私は事前にwrong.Thanksをつもりどこだから、誰も私を教えてくださいすることができます

import java.util.Scanner; 

public class LongestIncreasingSubSequence { 

    public static int BS(int[] arr,int low,int high,int key){ 

     int mid; 

     while ((high - low) > 1) { 

      mid = (int) Math.ceil((low + high)/2); 

      if (arr[mid] >= key) { 
       high = mid; 
      } else { 
       low = mid; 
      } 
     } 
     return high; 
    } 

    public static void main(String[] args) { 

     Scanner sc = new Scanner(System.in); 
     int n; 
     n = sc.nextInt(); 
     int arr[] = new int[n]; 
     int LS[] = new int[arr.length]; 
     int count = 1; 

     for (int i = 0; i < n; i++) { 
      arr[i] = sc.nextInt(); 
     } 
     LS[0] = arr[0]; 

     for (int i = 1; i < arr.length; i++) { 
      if (arr[i] < LS[0]) { 
       LS[0] = arr[i]; 
      } else if (arr[i] > LS[count-1]) { 
       LS[count++] = arr[i]; 
      } else { 
       LS[BS(arr,0,count-1,arr[i])] = arr[i]; 
      } 
     } 
     System.out.println(count); 
    } 
} 

、私のコードです。我々は増加サブシーケンスの各々の長さ（すなわち、LSある）の最小値を持つ配列を更新する必要があるため
LS[BS(arr,0,count-1,arr[i])] = arr[i];は、代わり
LS[BS(LS,0,count-1,arr[i])] = arr[i];であるべきではなく、元のもの：ここでバグがあり

Answer 1

。 この変更で、テストケースで正しく動作します（私はそれを他のものでテストしていませんが、アルゴリズムは今私には正しいと思われます）。