Problem statement:

Given a number sequence, find the length of its Longest Bitonic Subsequence (LBS). A subsequence is considered bitonic if it is monotonically increasing and then monotonically decreasing.

Example:

Input: {4,2,3,6,10,1,12}
Output: 5
Explanation: The LBS is {2,3,6,10,1}.

Input: {4,2,5,9,7,6,10,3,1}
Output: 7
Explanation: The LBS is {4,5,9,7,6,3,1}.

Solution Memo

private int findLBSLength(int[] nums) {
  int maxLength = 0;
  for(int i=0; i<nums.length; i++) {
    int c1 = findLDSLength(nums, i, -1);
    int c2 = findLDSLengthRev(nums, i, -1);
    maxLength = Math.max(maxLength, c1+c2-1);
  }
  return maxLength;
}

// find the longest decreasing subsequence from currentIndex till the end of the array
private int findLDSLength(int[] nums, int currentIndex, int previousIndex) {
  if(currentIndex == nums.length)
    return 0;

  // include nums[currentIndex] if it is smaller than the previous number
  int c1 = 0;
  if(previousIndex == -1 || nums[currentIndex] < nums[previousIndex])
    c1 = 1 + findLDSLength(nums, currentIndex+1, currentIndex);

  // excluding the number at currentIndex
  int c2 = findLDSLength(nums, currentIndex+1, previousIndex);

  return Math.max(c1, c2);
}

// find the longest decreasing subsequence from currentIndex till the beginning of the array
private int findLDSLengthRev(int[] nums, int currentIndex, int previousIndex) {
  if(currentIndex < 0)
    return 0;

  // include nums[currentIndex] if it is smaller than the previous number
  int c1 = 0;
  if(previousIndex == -1 || nums[currentIndex] < nums[previousIndex])
    c1 = 1 + findLDSLengthRev(nums, currentIndex-1, currentIndex);

  // excluding the number at currentIndex
  int c2 = findLDSLengthRev(nums, currentIndex-1, previousIndex);

  return Math.max(c1, c2);
}

Solution Bottom UP

int longestBitonicSubsequenceBU(int[] arr) {
    int n = arr.length;
    int[] lds = new int[n];
    int[] ldsRev = new int[n];

    //go left
    for (int i = 0; i < n; i++) {
        lds[i] = 1; //for one letter min subsequence = 1
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                lds[i] = Math.max(lds[i], 1 + lds[j]);
            }
        }
    }

    //go right
    for (int i = n - 1; i >= 0; i--) {
        ldsRev[i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                ldsRev[i] = Math.max(ldsRev[i], 1 + ldsRev[j]);
            }
        }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, lds[i] + ldsRev[i] - 1);
    }
    return max;
}

Time complexity:

O(N^2)

Space complexity:

O(N^2) → O(N)

Approach:

find longest decreasing in both sides; for dp: init two arrays and go left in first(i = 0; i++; j = i - 1; j—) and go right in second (i = n - 1;i—;j = i + 1;j++); find longest decreasing subsequence; then in for loop combine math from both indices + 1