Find the length of longest bitonic subsequence in an array

Algorithm/Insights

The problem can be solved by using longest increasing subsequence strategy.
Please go through this post on finding longest increasing subsequence:
Longest Increasing Subsequence

Algorithm for finding longest bitonic subsequence:
1. Given input array of length n.
2. Create array lisLength[] where lisLength[i] = Length of Longest Increasing Subsequence in input[0..i] including ith element
3. Create array ldsLength[] where ldsLength[i] = Length of Longest Decreasing Subsequence in input[i..n-1] including ith element
Then length of longest increasing bitonic subsequence which includes the ith element can be calculated as:
        lisLength[i] + ldsLength[i] - 1
Here 1 is subtracted from the sum of lengths because ith element is counted twice.
Therefore, length of longest bitonic subsequence is the maximum value for i = 0..n-1
        max(lisLength[i] + ldsLength[i] - 1)

Example:
input array:


lisLength[] : [1, 0, 0, 0, 0, 0, 0, 0]

i = 1: lisLength[1] = 1
    j = 0: input[0] = 12 < input[1] = 18, also lisLength[1] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[1] = lisLength[0] + 1 = 2
lisLength[] : [1, 2, 0, 0, 0, 0, 0, 0]

i = 2: lisLength[2] = 1
    j = 0: input[0] = 12 > input[2] = 7
    j = 1: input[1] = 18 > input[2] = 7
lisLength[] : [1, 2, 1, 0, 0, 0, 0, 0]

i = 3: lisLength[3] = 1
    j = 0: input[0] = 12 < input[3] = 34, also lisLength[3] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[3] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[3] = 34, also lisLength[3] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[3] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[3] = 34, but lisLength[3] = 3 > lisLength[2] + 1 = 2, so lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 0, 0, 0, 0]

i = 4: lisLength[4] = 1
    j = 0: input[0] = 12 < input[4] = 30, also lisLength[4] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[4] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[4] = 30, also lisLength[4] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[4] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[4] = 30, but lisLength[4] = 3 > lisLength[2] + 1 = 2, so lisLength is not updated.
    j = 3: input[3] = 34 > input[4] = 30
lisLength[] : [1, 2, 1, 3, 3, 0, 0, 0]

i = 5: lisLength[5] = 1
    j = 0: input[0] = 12 < input[5] = 28, also lisLength[5] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[5] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[5] = 28, also lisLength[5] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[5] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[5] = 28, but lisLength[5] = 3 > lisLength[2] + 1, so lisLength is not updated.
    j = 3: input[3] = 34 > input[5] = 28
    j = 4: input[4] = 30 > input[5] = 28
lisLength[] : [1, 2, 1, 3, 3, 3, 0, 0]

i = 6: lisLength[6] = 1
    j = 0: input[0] = 12 < input[6] = 90, also lisLength[6] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[6] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[6] = 90, also lisLength[6] = 2 < lisLength[1] + 1 = 3, so we update:
        lisLength[6] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[6] = 90, but lisLength[6] = 3 > lisLength[2] + 1, so lisLength is not updated.
    j = 3: input[3] = 34 < input[6] = 90, also lisLength[6] = 3 < lisLength[3] + 1 = 4, so we update:
        lisLength[6] = lisLength[3] + 1 = 4
    j = 4: input[4] = 30 < input[6] = 90, but lisLength[6] = 4 = lisLength[4] + 1, so lisLength is not updated.
    j = 5: input[5] = 28 < input[6] = 90, but lisLength[6] = 4 = lisLength[5] + 1, so lisLength is not updated.
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 0]

i = 7: lisLength[7] = 1
    j = 0: input[0] = 12 < input[7] = 88, also lisLength[7] = 1 < lisLength[0] + 1 = 2, so we update:
        lisLength[7] = lisLength[0] + 1 = 2
    j = 1: input[1] = 18 < input[7] = 88, also lisLength[7] = 1 < lisLength[1] + 1 = 3, so we update:
        lisLength[7] = lisLength[1] + 1 = 3
    j = 2: input[2] =  7 < input[7] = 88, but lisLength[7] = 3 > lisLength[2] + 1, so lisLength is not updated.
    j = 3: input[3] = 34 < input[7] = 88, also lisLength[7] = 3 < lisLength[3] + 1 = 4, so we update:
        lisLength[7] = lisLength[3] + 1 = 4
    j = 4: input[4] = 30 < input[7] = 88, but lisLength[7] = 4 = lisLength[4] + 1, so lisLength is not updated.
    j = 5: input[5] = 28 < input[7] = 88, but lisLength[7] = 4 = lisLength[5] + 1, so lisLength is not updated.
    j = 6: input[6] = 90 > input[7] = 88
lisLength[] : [1, 2, 1, 3, 3, 3, 4, 4]

Similarly, longest decreasing subsequence length array is computed as follows:

ldsLength[] : [0, 0, 0, 0, 0, 0, 0, 1]

i = n-2 = 6: ldsLength[6] = 1
    j = n-1 = 7: input[7] = 88 < input[6] = 90
       ldsLength[6] = ldsLength[7] + 1 = 2
ldsLength[] : [0, 0, 0, 0, 0, 0, 2, 1]

i = 5: ldsLength[5] = 1
    j = 7: input[7] = 88 > input[5] = 28
    j = 6: input[6] = 90 > input[5] = 28
ldsLength[] : [0, 0, 0, 0, 0, 1, 2, 1]

i = 4: ldsLength[4] = 1
    j = 7: input[7] = 88 > input[5] = 30
    j = 6: input[6] = 90 > input[5] = 30
    j = 5: input[5] = 28 < input[5] = 30
       ldsLength[4] = ldsLength[5] + 1 = 2
ldsLength[] : [0, 0, 0, 0, 2, 1, 2, 1]

i = 3: ldsLength[3] = 1
    j = 7: input[7] = 88 > input[5] = 34
    j = 6: input[6] = 90 > input[5] = 34
    j = 5: input[5] = 28 < input[5] = 34
       ldsLength[3] = ldsLength[5] + 1 = 2
    j = 4: input[4] = 30 < input[5] = 34
       ldsLength[3] = ldsLength[4] + 1 = 3
ldsLength[] : [0, 0, 0, 3, 2, 1, 2, 1]

i = 2: ldsLength[2] = 1
    j = 7: input[7] = 88 > input[5] = 7
    j = 6: input[6] = 90 > input[5] = 7
    j = 5: input[5] = 28 > input[5] = 7
    j = 4: input[4] = 30 > input[5] = 7
    j = 3: input[3] = 34 > input[5] = 7
ldsLength[] : [0, 0, 1, 3, 2, 1, 2, 1]

i = 1: ldsLength[1] = 1
    j = 7: input[7] = 88 > input[5] = 18
    j = 6: input[6] = 90 > input[5] = 18
    j = 5: input[5] = 28 > input[5] = 18
    j = 4: input[4] = 30 > input[5] = 18
    j = 3: input[3] = 34 > input[5] = 18
    j = 2: input[2] =  7 < input[5] = 18
       ldsLength[2] = ldsLength[2] + 1 = 2
ldsLength[] : [0, 2, 1, 3, 2, 1, 2, 1]

i = 0: ldsLength[0] = 1
    j = 7: input[7] = 88 > input[5] = 12
    j = 6: input[6] = 90 > input[5] = 12
    j = 5: input[5] = 28 > input[5] = 12
    j = 4: input[4] = 30 > input[5] = 12
    j = 3: input[3] = 34 > input[5] = 12
    j = 2: input[2] =  7 < input[5] = 12
       ldsLength[2] = ldsLength[2] + 1 = 2
    j = 1: input[1] = 18 > input[5] = 12
ldsLength[] : [2, 2, 1, 3, 2, 1, 2, 1]

lisLength[] : [1, 2, 1, 3, 3, 3, 4, 4]
ldsLength[] : [2, 2, 1, 3, 2, 1, 2, 1]

Finally, length of longest bitonic subsequence is calculated:
lisLength[1] + ldsLength[1] - 1  =  2 + 2 - 1  =  3
lisLength[2] + ldsLength[2] - 1  =  1 + 1 - 1  =  1
lisLength[3] + ldsLength[3] - 1  =  3 + 3 - 1  =  5
lisLength[4] + ldsLength[4] - 1  =  3 + 2 - 1  =  4
lisLength[5] + ldsLength[5] - 1  =  3 + 1 - 1  =  3
lisLength[6] + ldsLength[6] - 1  =  4 + 2 - 1  =  5    ---> MAXIMUM
lisLength[7] + ldsLength[7] - 1  =  4 + 1 - 1  =  4

Hence, solution = 5
As can be seen from any of the following bitonic subsequences.

Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Find the length of longest bitonic subsequence in an array
 *
 * @author Saurabh
 */
public class LongestBitonicSubsequence {

    public static int longestBitonicSubsequence(int[] input) {
    	
    	if(input == null || input.length == 0) {
    		return 0;
    	}
    	
    	int n = input.length;
    	// lisLength[i] = Length of Longest Increasing Subsequence in input[0..i]
        int[] lisLength = new int[n];
        // ldsLength[i] = Length of Longest Increasing Subsequence in input[i..n-1]
        int[] ldsLength = new int[n];
        int maxLength = 1;

        // Find lengths of longest increasing subsequence for all sub arrays [0..i]
        lisLength[0] = 1;
        for (int i = 1; i < n; i++) {
        	lisLength[i] = 1;
            for (int j = 0; j < i; j++) {
                if (input[i] > input[j] && lisLength[i] < lisLength[j] + 1) {
                    lisLength[i] = lisLength[j] + 1;
                }
            }
        }

        // Find lengths of longest decreasing subsequence for all sub arrays [i..n-1]
        ldsLength[n-1] = 1;
        for (int i = n - 2; i >= 0; i--) {
        	ldsLength[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (input[i] > input[j] && ldsLength[i] < ldsLength[j] + 1) {
                    ldsLength[i] = ldsLength[j] + 1;
                }
            }
        }

        for (int i = 1; i < n; i++) {
            if (maxLength < lisLength[i] + ldsLength[i] - 1)
                maxLength = lisLength[i] + ldsLength[i] - 1;
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] array = { 12, 18, 7, 34, 30, 28, 90, 88 };
        System.out.println("Length of Longest Bitonic Subsequence: " + longestBitonicSubsequence(array));
    }
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n)