使用二分查找求最长递增子序列

Question

我正在尝试使用二分搜索实现最长上升子序列。我已经编写了算法并且我的测试用例得到了满足，但是当我提交代码时，它在一些测试用例中失败，例如对于以下列表： 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);
    }
}

所以，有人可以告诉我哪里出了错吗？谢谢提前。

- Sai Sankalp

---

首先输入数组中整数的数量，然后在下一行中给出整数序列。 - Sai Sankalp

在子序列中，您不允许改变顺序。所以 LS[0] = arr[i]; 不起作用，因为 LS[1] 可能是 arr[i-1]。 - njzk2

为什么不打印出找到的序列，这可能有助于确定那个额外的元素是来自开头还是结尾，或者是重复的。 - weston

不，我不会改变顺序，我的算法是这样的：我将取出数组中的下一个元素并将其与第一个元素进行比较，如果它是最小的，我将替换该元素；如果LS的末尾小于当前元素，则将其附加到数组的末尾，否则我将执行二分查找以找到元素的正确位置。 - Sai Sankalp

是的，你说得对，但我写这个程序是为了找到数组的长度，而不是实际的序列。对于 {2,3,1} 这个数组，我得到了正确的输出，即 2。 - Sai Sankalp

Answer 1

这里有一个bug：
LS[BS(arr,0,count-1,arr[i])] = arr[i];应该改为
LS[BS(LS,0,count-1,arr[i])] = arr[i];，因为我们需要更新数组中每个递增子序列的最小值（即LS），而不是原始数组。 经过这个更改，在您的测试用例上可以正常工作（我还没有在其他任何地方进行测试，但现在算法看起来是正确的）。

- kraskevich

---

是的，你说得对。我的错误。现在它正常工作了。谢谢你的帮助 :)。 - Sai Sankalp