Longest Bitonic Sequence - Algorithms and Problem SolvingAlgorithms and Problem Solving

Longest Bitonic Sequence - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a sequence as as array of positive integers. Find the length of longest bitonic subsequence.

A bitonic subsequence is a subsequence that is first increasing up to a peak value and then decreasing from the peak value. For example, A=[1, 11, 2, 10, 4, 5, 2, 1] the longest bitonic sequence is 1, 2, 4, 5, 2, 1 of length 6. For A=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] longest bitonic sequence is 0, 8, 12, 14, 13, 11, 7 of length 7.

Note that a bitoic sequence starting from a value reaches a peak value in a strict increasing order of values. Then it start decreasing monotonically. So, we can easily perceive that a bitonic sequence consists of a increasing subsequence and a decreasing subsequence. So, a longest bitonic subsequence would be subsequence that consists of a longest increasing subsequence (LIS) ending at peak and a longest decreasing subsequence (LDS) starting at peak. For example longest bitonic subsequence of A=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] can be represented as follows.

  LIS     peak    LDS     |       |       |     |       v       |     |      14       |     v   12    13    v       8         11     0             7  

So, the longest bitonic subsequence with peak at a position i would consists of longest increasing subsequence that ends at i and a longest decreasing subsequence starting at i. We need to construct two arrays LIS[] and LDS[] such that for each position i –

   	LIS[i] : length of the Longest Increasing subsequence ending at arr[i].   	LDS[i]:  length of the longest Decreasing subsequence starting from arr[i].                   LIS[i]+LDS[i]-1 : the length Longest Bitonic Subsequence with peak at i.  

We need to find the position i with maximum value of LIS[i]+LDS[i]-1. We can easily solve this problem by solving the Longest Increasing Subsequence (LIS) problem.

Longest Increasing Subsequence (LIS) – Dynamic Programming
First of all, lets focus how to compute longest increasing subsequence. Let's consider LIS(i) be the length of longest increasing subsequence of the sequence at position i i.e. A[0..i] where A is the input sequence.

For example, A=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] –

LIS(0) = 1  [0]  ---> a singe number is an increasing subsequence itself  LIS(1) = 2  [0, 8]  LIS(2) = 2  [0,4]  LIS(3) = 3  [0, 8, 12] or [0, 4, 12]  LIS(4) = 2  [0, 2]  LIS(5) = 3  [0, 8, 10] or [0, 4, 10] or [0, 2, 10]  LIS(6) = 3  [0, 4, 6] or [0, 2, 6]  LIS(7) = 4  [0, 8, 12, 14] or [0, 4, 12, 14] or [0, 8, 10, 14] or [0, 4, 10, 14] or [0, 4, 6, 14] or [0, 2, 6, 14]  ....  ....  

Note that, LIS(7) is constructed by appending A[7] to the solutions of LIS(3), LIS(5), and LIS(6). If we look closely to other solutions then we will se that LIS(i) is constructed by appending A[i] to the maximum length solutions LIS(j) for all j < i and A[j] < A[i]. So, we can construct a recurrence relation LIS(i) = max{1+LIS(j)} for all j < i and A[j] < A[i] . The recursion tree for the above recurrence for i = 4 is as follows –

                           lis(4)                              /       |      \           lis(3)      lis(2)    lis(1)            /     \        /             lis(2)  lis(1)   lis(1)     /      lis(1)   

So, the LIS problem has an optimal substructure LIS(i) = max{1+LIS(j)} for all j < i and the subproblems are repeating. So, we can use a Dynamic Programming (DP) table to cache the result and reuse computations.

Longest Decreasing Subsequence (LDS) can be computed similar to LIS with the recurrence relation LDS(i) = max{1+LDS(j)} for all j < i and A[j] > A[i] . Using these two relations we can now easily compute Longest Bitonic Sequence with peak at i by LIS(i)+LDS(i)-1. We need to find a peak position i such that the value of LIS(i)+LDS(i)-1 is maximized. Following is a simple implementation of the idea which runs in O(n^2) time and O(n) auxiliary space.

Read full article from Longest Bitonic Sequence - Algorithms and Problem SolvingAlgorithms and Problem Solving