Obsidian Notes

Longest Bitonic Sequence

3 min read

Problem statement

A Bitonic Sequence is a sequence of numbers that is first strictly increasing and then strictly decreasing.
A strictly ascending order sequence is also considered bitonic, with the decreasing part as empty, and same for a strictly descending order sequence.

For example, the sequences [1, 3, 5, 3, 2], [1, 2, 3, 4] are bitonic, whereas the sequences [5, 4, 1, 4, 5] and [1, 2, 2, 3] are not.

You are given an array ‘arr’ consisting of ‘n’ positive integers.

Find the length of the longest bitonic subsequence of ‘arr’.
Example :

Input: 'arr' = [1, 2, 1, 2, 1]

Output: 3

Explanation: The longest bitonic subsequence for this array will be [1, 2, 1]. Please note that [1, 2, 2, 1] is not a valid bitonic subsequence, because the consecutive 2's are neither strictly increasing, nor strictly decreasing.

Detailed explanation ( Input/output format, Notes, Images )

Sample Input 1 :
5 
1 2 1 2 1
Sample Output 1:
3

Explanation For Sample Input 1:

The longest bitonic subsequence for this array will be [1, 2, 1]. Please note that [1, 2, 2, 1] is not a valid bitonic subsequence, because the consecutive 2's are neither strictly increasing, nor strictly decreasing.
Sample input 2 :
5
1 2 1 3 4
Sample Output 2 :
4

Explanation For Sample Input 2:

The longest bitonic sequence for this array will be [1, 2, 3, 4].
Expected time complexity :
The expected time complexity is O(n ^ 2).
Constraints:
1 <= 'n' <= 10^3
1 <= 'arr[i]' <= 10^5

Approach - Bottom Up

  • Find LIS and then LDS and then combine
  • O(n^2), O(n)
class Solution {
    public int longestBitonicSubsequence(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n]; // Longest Increasing Subsequence up to i
        int[] lds = new int[n]; // Longest Decreasing Subsequence from i
 
        // Step 1: Fill LIS
        Arrays.fill(lis, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    lis[i] = Math.max(lis[i], lis[j] + 1);
            }
        }
 
        // Step 2: Fill LDS
        Arrays.fill(lds, 1);
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[j] < nums[i])
                    lds[i] = Math.max(lds[i], lds[j] + 1);
            }
        }
 
        // Step 3: Combine LIS and LDS
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            maxLen = Math.max(maxLen, lis[i] + lds[i] - 1);
        }
 
        return maxLen;
    }
}

Backlinks