我正在尝试使用二进制搜索实现最长递增子序列。好吧,我已经编写了算法并且我的测试用例得到了满足,但是当我提交代码时,某些测试用例失败了,例如下面的列表,
29471 5242 21175 28931 2889 7275 19159 21773 1325 6901,答案应该是 4 但我得到 5。下面是我的代码,
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);
}
}
所以任何人都可以告诉我哪里出错了。提前致谢。
最佳答案
这里有个bug:
LS[BS(arr,0,count-1,arr[i])] = arr[i];
应该是
LS[BS(LS,0,count-1,arr[i])] = arr[i];
相反,因为我们需要用递增的每个长度的最小值更新数组子序列(即 LS
),而不是原始序列。
通过此更改,它可以在您的测试用例上正常工作(我还没有在其他任何东西上测试过它,但算法现在对我来说看起来是正确的)。
关于java - 使用二进制搜索的最长递增子序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39920015/