使用二进制搜索的最长增加子序列

我正在尝试使用二进制搜索来实现最长增加子序列。嗯，我的编码算法和我的测试案例越来越满意，但是当我提交的代码，它失败了一些测试情况下，像例如，对于下面的列表，使用二进制搜索的最长增加子序列

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

是的，你是正确的。我的错误，现在工作很好。谢谢你的帮助:)。 –

使用二进制搜索的最长增加子序列

回答

相关问题