1

サブシーケンスが単調に増加してから単調に減少する場合、または単調に増加してから単調に減少するように循環的にシフトできる場合、サブシーケンスはバイトニックです。

シーケンスが与えられた場合、最長のバイトニック サブシーケンスを効率的に決定するにはどうすればよいですか?

編集: タイトルをサブシーケンスに編集

4

1 に答える 1

4

ここには、アルゴリズムの完全なコンパイル可能な例が含まれています。

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) の複雑さを使用します。これは与えられたものであり、このスレッドでは説明しません。

このメソッドは、O(n*logn) の複雑さを使用する LIS の動的プログラミング バージョンを使用します (ここでは説明しません) 動的 LIS アルゴリズムは、最長のサブ配列の長さを返します。わずかな変更を加えて、n のサイズの配列に、そのインデックスまでの最長のサブ配列の長さを保存します。

そのため、各インデックスで「インデックスまでの最大長」がわかります。次に、LDS についても同じことを行います。これにより、「インデックスからの最大長」の値が得られます

その後、値を相互結合します。これにより、「インデックスまでの最大長 + インデックスからの最大長」の値が得られます。

index の要素が 2 回計算されるため、1 つを削除します。したがって、次の式が得られます。

lbs[i] = lis[i]+lds[n-i]-1n>=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)

于 2016-01-29T02:30:04.070 に答える