1

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

Aravind
  • 3,169
  • 3
  • 23
  • 37
HazirBot
  • 323
  • 2
  • 14
  • 1
    A deleted answer (which is link-only, and so correctly deleted) points at [this claimed O(n) solution](http://www.geeksforgeeks.org/maximum-length-bitonic-subarray/). Somebody should feel free to summarize the interesting insights from that page here. – Daniel Wagner Jan 29 '16 at 03:10
  • i've yet to confirm a method that returns in O(n) time, they usually fall for the example array i've given in the code. thanks for the lovely edit, you really made the whole thing much clearer! the one in the link you provided + some of the ones i checked in the comments result in 4 instead of 6. these O(n) methods just don't deal well with arrays that have several peaks to them mostly since they don't incorporate the basic principles of LIS algorithm, they're mostly greedy based. – HazirBot Jan 29 '16 at 03:37
  • 1
    @GiladMitrani: It's very easy to feel complacent about the solution we came up. The solution given in that link is correct. Perhaps you don't understand the question in the link. There is a difference between Longest Bitonic Subarray and Longest Bitonic Subsequence. For subarray(meaning elements must be contiguous) the optimal solution is in O(N). – Aravind Jan 29 '16 at 04:40
  • I indeed did not understand the difference in question. I've edited my original post title to better fit this new-found knowledge. thank you for pointing that out. – HazirBot Jan 29 '16 at 05:11

1 Answers1

4

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)

HazirBot
  • 323
  • 2
  • 14
  • Is your solution for the longest bitonic subsequence or for the longest bitonic subarray problem? – Aravind Jan 29 '16 at 03:27
  • Also, can you explain how the binary search works in getting the LIS? binary search is for sorted arrays, how is the input array to it sorted? I followed the code, but a bit of explanation can help me understand it much faster. – Aravind Jan 29 '16 at 03:34
  • @Aravind My solution give the `length` of the longest bitonic sub array. Dynamic programing LIS incorporates binary search to reduce the amount of checks required to find the correct location of the last read element. the original array is not sorted, but the array in which the sub array is stored is. the binary search takes place in that sorted auxiliary array. I hope that helps :P – HazirBot Jan 29 '16 at 03:41
  • Your solution does not compute Longest Bitonic Subarray. Perhaps, you are trying Longest Bitonic Subsequence problem. Can you clearly state the problem you have solved? – Aravind Jan 29 '16 at 04:40
  • @Aravind you are correct, that was a translation error for me. edited. – HazirBot Jan 29 '16 at 05:09
  • for each lds[i], is it representing the LDS ending at i or starting i? in ldsArray, feels like we should do t[i]=arr[size-i-1](instead of -arr[i]? – Hui Liu Jun 04 '17 at 13:22