Longest Bitonic Sequence

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.

public static int longestBiotonicSequence(int[] a){
	int[] lis = new int[a.length];
	int[] lds = new int[a.length];
	//base cases - single number is a lis and lds
	Arrays.fill(lis, 1);
	Arrays.fill(lds, 1);
	int maxBiotonicLen = Integer.MIN_VALUE;
	
	//longest increasing subsequence
	//lis(i) = max{1+lis(j)}, for all j < i and a[j] < a[i]
	for(int i = 1; i < a.length; i++){
		for(int j = 0; j < i; j++){
			if(a[i] > a[j] && lis[j] + 1 > lis[i]){
				lis[i] = lis[j]+1;
			}
		}
	}
	
	//longest decreasing subsequence
	//lds(i) = max{1+lds(j)}, for all j < i and a[j] > a[i]
	//longest biotonic seq lbs(i) = lis(i)+lds(i)-1
	maxBiotonicLen = lis[0]+lds[0]-1;
	for(int i = 1; i < a.length; i++){
		for(int j = 0; j < i; j++){
			if(a[i] < a[j] && lds[j] + 1 > lds[i]){
				lds[i] = lds[j]+1;
			}
		}
		maxBiotonicLen = Math.max(maxBiotonicLen, lis[i]+lds[i]-1);
	}
	
	return maxBiotonicLen;
}