Longest bitonic subsequence in O(n*logn) complexity

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.

Given a sequence, how can I determine the longest bitonic subsequence efficiently?

edit: edited title to subsequence

Answer 1

here included a complete compilable example of the algorithm:

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

explanation:

first of all a binary search uses a complexity of O(logn), it is a given an i shall not explain this in this thread.

This method uses a dynamic programming version of LIS which uses a complexity of O(n*logn) (also a given that shall not be explained here) a dynamic LIS algorithm returns the length of the longest sub-array. with slight modification we save into an array the size of n the longest sub-array length up to and including that index.

so in each index we know "the max length up to index" next we do the same for LDS. this will give us the value of "the max length from index"

afterwards we cross-combine the values, this gives us the value of "the max length up to index + the max length from index"

now since the element in index is calculated twice we remove one. thus resulting in the formula:

lbs[i] = lis[i]+lds[n-i]-1 for n>=1;

as for complexity the following commands:

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

each work O(n*logn) complexity

and the for loop:

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

works in O(n) complexity so the total is O(n*logn)+O(n*logn)+O(n) = O(n*logn)