Найти самую длинную возрастающую подпоследовательность с соседними элементами, имеющими разность не менее k

Question

Учитывая массив A размера n и число k, найдите размер самой длинной возрастающей подпоследовательности (скажем, B[]), где B[i+1] >= B[i] + k.

2 <= n <= 10^6
A[i] <= 10^5
k <= 10^5

Пример ввода:

A = [1, 3, 1, 4, 5, 9, 12]
k = 2
The LIS in this case will be: [1, 3, 5, 9, 12]
Answer = 5

Как решить по сложности O(N * log(N)) (или лучше)?Ниже описан мой подход O(N^2 * log(N)):

Я буду использовать структуру данных, аналогичную std::multiset (в C ++).std::multiset гарантирует, что все элементы в мультимножестве будут отсортированы в любой момент времени.

Я создам мультимножество пар std::multiset <pair <int, int> > V, где первым элементом в паре будет элемент измассив A, а второй элемент будет иметь размер самой длинной возрастающей подпоследовательности, так что LIS заканчивается в первом элементе пары.Кроме того, в каждом случае первая пара в мультимножестве будет <-∞, 0>.

int answer() {

    multiset < pair < int, int> > V;
    V.insert(<-∞, 0>);
    final_answer = 1

    for (element e) in A {
        maximum_possible = 1

        for (pair p) in V {
            if (p.first > e - k)
                break;
            maximum_possible = max(p.second + 1, maximum_possible)
        }
        V.insert(<A[i], maximum_possible>)
        final_answer = max(final_answer, maximum_possible)
    }

    return final_answer;
}

Answer 1

Вы можете сделать это аналогично обычной проблеме LIS.Алгоритм:

 1. Make an empty dynamic array (or anything that you can push back elements into in O ( 1 ) and that gives you access to any element in O(1) ), let's call it DP
 2. For every number v in the input array:
      3. Search DP array for a value smaller or equal to v - k and set a variable id as it's id number in the DP array (using binary search, if it does not exist, set id as -1)
      4. Increase id by 1
      5. If size of DP is equal id, insert there a new value, that is v
          Else if DP[id] > v, change it to v.
 6. Return size of DP.

Вот и все, O (n log n).

Answer 2

Вы можете сделать это в O(N^2), используя стандартное динамическое программирование для LIS: Только изменение вместо nums[i] > nums[j] в условии if, просто измените его на nums[i] - nums[j] >= K

    public int lengthOfLISAtLeastKUsingDP(int[] nums, int K) {
        int[] dp = new int[nums.length+1];
        Arrays.fill(dp, 1);
        int ans = 0;
        for ( int i = 0; i < nums.length; i++ ) {
            for ( int j = 0; j < i; j++ ) {
                if ( nums[i] - nums[j] >= K ) {
                    dp[i] = Math.max( dp[i], 1 + dp[j] );
                }
            }
            ans = Math.max( ans, dp[i] ); 
        }
        return ans;
    }

Сказав это, я полагаю, вы могли бы сделать это в O(N*log(N)) так:

1. Создать пустой список.
2. Добавление первого элемента в список.
3. Обход списка, если вы столкнулись с элементом, который больше, чем последний элемент списка более чем на K или равен ему, добавьте его в список.
4. Если это не так, то выполнить бинарный поиск в списке для этого элемента, если он найден, делать нечего.
5. В противном случае посмотрите на точку вставки. Точка вставки либо больше, чем размер списка, либо меньше его.
6. Если он больше, чем размер И, если разница между этим элементом и последним элементом в списке больше, чем K, добавьте его в список.
7. Если точка вставки равна нулю, просто замените 0-й элемент.
8. Но если точка вставки не равна нулю, посмотрите на ее левый элемент. Если их разность больше или равна K, вставьте туда элемент.
9. Размер полученного списка является ответом.

public int lengthOfLISAtLeastK(int[] nums, int K) {
    if ( nums == null ) return 0;
    if ( nums.length <= 1 ) return nums.length;
    List<Integer> list = new ArrayList<Integer>(nums.length);
    list.add( 0, nums[0] );
    for ( int i = 1; i < nums.length; i++ ) {
        if ( nums[i] - list.get( list.size() - 1 ) >= K ) {
            list.add( nums[i] );
        } else  {
            int index = Collections.binarySearch( list, nums[i] );
            if ( index >= 0 && index < nums.length ) {
                list.set( index, nums[i] );
            } else {
                if ( -index - 1 > list.size() - 1 ) {
                    if ( nums[i] - list.get(list.size()-1) >= K ) {
                        list.add(nums[i]);
                    }
                } else {
                     if ( -index - 1 == 0 ) {
                        list.set(-index-1, nums[i]);
                    } else if ( nums[i] - list.get(-index-2) >= K ) {
                        list.set(-index-1, nums[i]);
                    }
                }
            }
        }
    }
    return list.size();
}