O(n*logn) 复杂度中的最长双调子序列

Question

A subsequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically increase and then monotonically decrease.

给定一个序列，如何有效地确定最长的双调子序列？

编辑：编辑了子序列的标题

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算法returns最长子数组的长度。稍作修改，我们将最长的子数组长度保存到一个数组中，直到并包括该索引。

所以在每个索引中我们都知道 "the max length up to index" 接下来我们对 LDS 做同样的事情。这将为我们提供 "the max length from index"

的值

之后我们交叉组合这些值，这给了我们 "the max length up to index + the max length from index"

的值

现在，由于索引中的元素被计算了两次，我们删除了一个。从而得出公式：

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)

O(n*logn) 复杂度中的最长双调子序列

Longest bitonic subsequence in O(n*logn) complexity

java

algorithm

lds

lis