使用二進制搜索的最長增加子序列

我正在嘗試使用二進制搜索來實現最長增加子序列。嗯，我的編碼算法和我的測試案例越來越滿意，但是當我提交的代碼，它失敗了一些測試情況下，像例如，對於下面的列表，使用二進制搜索的最長增加子序列

29471 5242 21175 28931 2889 7275 19159 21773 1325 6901，答案應該是4，但我得到5.Below是我的代碼，

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); 
    } 
}

因此，誰能告訴我在哪裏，我提前去wrong.Thanks。

來源

2016-10-07 Sai Sankalp

第一次輸入將是數組中的整數和下一行，我們將給出整數序列。 –

在子序列中，您不能更改順序。所以'LS [0] = arr [i];'不起作用，因爲'LS [1]'可能是'arr [i-1]' – njzk2

爲什麼不打印出找到的序列呢？如果多餘的一個是從開始或結束，或重複。 – weston

這裏有一個錯誤：
LS[BS(arr,0,count-1,arr[i])] = arr[i];應該
LS[BS(LS,0,count-1,arr[i])] = arr[i];代替，因爲我們需要更新與增加的子序列的每個長度（即LS）的最小值的數組，而不是原來的。有了這個改變，它可以在你的測試用例上正常工作（我還沒有在其他任何地方測試過，但現在算法看起來是正確的）。

來源

2016-10-07 22:13:26 kraskevich

是的，你是正確的。我的錯誤，現在工作很好。謝謝你的幫助:)。 –

使用二進制搜索的最長增加子序列

回答

相關問題