Самая длинная битовая подпоследовательность в сложности O(n*logn)

Question

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

Учитывая последовательность, как я могу эффективно определить самую длинную битоническую подпоследовательность?

редактировать: отредактированный заголовок к подпоследовательности

Answer 1

Здесь включен полный скомпилированный пример алгоритма:

import java.util.Arrays;

public class LBS {

public static int binarySearchBetween(int[] arr, int end, int val) {
    int low = 0, high = end;
    if (val < arr[0]) {
        return 0;
    }
    if (val > arr[end]) {
        return end + 1;
    }
    while (low <= high) {
        int mid = (low + high) / 2;
        if (low == high) {
            return low;
        } else {
            if (arr[mid] == val) {
                return mid;
            }
            if (val < arr[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

/**
 * Returns an array of LIS results such that arr[i] holds the result of the 
 * LIS calculation up to that index included.
 * @param arr The target array.
 * @return An array of LIS results.
 */
public static int[] lisArray(int[] arr) { // O(n*logn) 
    /* Regular LIS */
    int size = arr.length;
    int[] t = new int[size]; 
    t[0]=arr[0];
    int end = 0;

    /* LIS ARRAY */
    int[] lis = new int[size]; // array for LIS answers.
     // Start at 1 (longest sub array of a single element is 1)
    lis[0]=1; 

    for (int i=1; i<size; i++) { // O(n) * O(logn) 
        int index = binarySearchBetween(t, end, arr[i]);
        t[index] = arr[i];
        if (index > end) {
            end++;
        }
        lis[i]=end+1; // saves the current calculation in the relevant index
    }
    return lis;
}

/*
* Input:  {1, 11, 2, 10, 4, 5, 2, 1}
* Output: {1,  2, 2,  3, 3, 4, 4, 4}
* Each index in output contains the LIS calculation UP TO and INCLUDING that 
* index in the original array.
*/

public static int[] ldsArray(int[] arr) { // O(n*logn)
    int size = arr.length;
    int t[] = new int[size];
    for (int i = 0; i < size; i++) {
        t[i] = -arr[i];
    }
    int ans[] = lisArray(t);
    return ans;
}

public static int lbs(int[] arr) { // O(n*logn)
    int size = arr.length;
    int[] lis = lisArray(arr); // O(n*logn)
    int[] lds = ldsArray(arr); // O(n*logn)
    int max = lis[0]+lds[size-1]-1;
    for (int i=1; i<size; i++) { // O(n)
        max = Math.max(lis[i]+lds[size-i]-1, max);
    }
    return max;
}

public static void main (String[] args)
{
        int arr[] = {1,11,2,10,4,5,2,1};
        System.out.println(Arrays.toString(arr));
        System.out.println(lbs(arr));
}
}

объяснение:

Прежде всего, бинарный поиск использует сложность O(logn), это дано, и я не буду объяснять это в этой теме.

В этом методе используется версия LIS с динамическим программированием, в которой используется сложность O(n*logn) (также данная информация, которая здесь не поясняется), алгоритм динамической LIS возвращает длину самого длинного подмассива. с небольшой модификацией мы сохраняем в массиве размер n самой длинной длины подмассива до этого индекса и включительно.

поэтому в каждом индексе мы знаем "максимальную длину до индекса", затем мы делаем то же самое для LDS. это даст нам значение "максимальная длина из индекса"

после этого мы объединяем значения, это дает нам значение "максимальная длина до индекса + максимальная длина от индекса"

Теперь, так как элемент в индексе рассчитывается дважды, мы удаляем один. что приводит к формуле:

lbs[i] = lis[i]+lds[n-i]-1 для n>=1;

Что касается сложности следующих команд:

int[] lis = lisArray(arr); // O(n*logn)
int[] lds = ldsArray(arr); // O(n*logn)

каждая работа O(n*logn) сложность

и цикл for:

for (int i=1; i<size; i++) { // O(n)
        max = Math.max(lis[i]+lds[size-i]-1, max);
    }

работает в O(n) сложность, так что общее O(n*logn)+O(n*logn)+O(n) = O(n*logn)