Самая длинная возрастающая подпоследовательность с использованием двоичного поиска

#java #algorithm

#java #алгоритм

Вопрос:

Я пытаюсь реализовать самую длинную возрастающую подпоследовательность с использованием двоичного поиска. Ну, я закодировал алгоритм, и мои тестовые примеры выполняются, но когда я отправляю код, он не работает для некоторых тестовых примеров, например, для следующего списка,

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

Итак, может кто-нибудь, пожалуйста, скажите мне, где я ошибаюсь.Заранее спасибо.

1. первым вводом будет количество целых чисел в массиве, а в следующей строке мы приведем последовательность целых чисел.

2. в подпоследовательности вам не разрешается изменять порядок. так LS[0] = arr[i]; что не работает, потому что возможно LS[1] , что arr[i-1]

3. Почему бы не распечатать найденную последовательность, это может помочь увидеть, является ли эта дополнительная последовательность начальной или конечной, или повторной.

4. нет, я не меняю порядок, мой алгоритм заключается в том, что я возьму следующий элемент в массиве и сравню его с первым элементом, если он наименьший, я заменю элемент, если конец LS меньше текущего элемента, я добавлю в конецв противном случае я выполню двоичный поиск, чтобы узнать правильное положение элемента

5. это en.wikipedia.org/wiki /… — это алгоритм того, что вы пытаетесь сделать. Это не похоже на то, что вы делаете.

Ответ №1:

Здесь есть ошибка:
LS[BS(arr,0,count-1,arr[i])] = arr[i]; должно быть
LS[BS(LS,0,count-1,arr[i])] = arr[i]; вместо этого, потому что нам нужно обновить массив наименьшим значением для каждой длины возрастающей подпоследовательности (то есть LS ), а не исходной. С этим изменением он работает правильно в вашем тестовом примере (я не тестировал его ни на чем другом, но теперь алгоритм выглядит правильным для меня).