Problem Statement

Given an array of n integers, the task is to find the length of the longest bitonic sequence. A sequence is considered bitonic if it first increases, then decreases. The sequence does not have to be contiguous.

Examples

Example 1:

Input: arr = [5, 1, 4, 2, 3, 6, 8, 7]
Output: 6

Explanation: The longest bitonic sequence is [1, 2, 3, 6, 8, 7] with the length of 6.

Example 2:

Input: arr = [10, 20, 30, 40, 50, 40, 30, 20]
Output: 8

Explanation: The entire array is bitonic, increasing up to 50 and then decreasing.

Different Approaches

1️⃣ Recursion (Exponential Time)

Code:

int LIS(int idx, int prev, vector<int>& arr) {
    if (idx == arr.size()) return 0;
    int take = 0;
    if (prev == -1 || arr[idx] > arr[prev])
        take = 1 + LIS(idx + 1, idx, arr);
    int notTake = LIS(idx + 1, prev, arr);
    return max(take, notTake);
}

int LDS(int idx, int prev, vector<int>& arr) {
    if (idx < 0) return 0;
    int take = 0;
    if (prev == -1 || arr[idx] > arr[prev])
        take = 1 + LDS(idx - 1, idx, arr);
    int notTake = LDS(idx - 1, prev, arr);
    return max(take, notTake);
}

int longestBitonicSubsequence(vector<int>& arr) {
    int n = arr.size();
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        int inc = LIS(0, -1, vector<int>(arr.begin(), arr.begin() + i + 1));
        int dec = LDS(n - 1, -1, vector<int>(arr.begin() + i, arr.end()));
        maxi = max(maxi, inc + dec - 1);
    }
    return maxi;
}

Complexity Analysis:

• Time Complexity: O(2^n)
• Space Complexity: O(n)

2️⃣ Memoization (Top-Down Approach)

Code:

int LIS(int idx, int prev, vector<int>& arr, vector<vector<int>>& dp) {
    if (idx == arr.size()) return 0;
    if (dp[idx][prev + 1] != -1) return dp[idx][prev + 1];

    int take = 0;
    if (prev == -1 || arr[idx] > arr[prev])
        take = 1 + LIS(idx + 1, idx, arr, dp);
    int notTake = LIS(idx + 1, prev, arr, dp);
    return dp[idx][prev + 1] = max(take, notTake);
}

int LDS(int idx, int prev, vector<int>& arr, vector<vector<int>>& dp) {
    if (idx < 0) return 0;
    if (dp[idx][prev + 1] != -1) return dp[idx][prev + 1];

    int take = 0;
    if (prev == -1 || arr[idx] > arr[prev])
        take = 1 + LDS(idx - 1, idx, arr, dp);
    int notTake = LDS(idx - 1, prev, arr, dp);
    return dp[idx][prev + 1] = max(take, notTake);
}

int longestBitonicSubsequence(vector<int>& arr) {
    int n = arr.size();
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        vector<vector<int>> dp1(n, vector<int>(n + 1, -1));
        vector<vector<int>> dp2(n, vector<int>(n + 1, -1));
        int inc = LIS(0, -1, vector<int>(arr.begin(), arr.begin() + i + 1), dp1);
        int dec = LDS(n - 1, -1, vector<int>(arr.begin() + i, arr.end()), dp2);
        maxi = max(maxi, inc + dec - 1);
    }
    return maxi;
}

Complexity Analysis:

• Time Complexity: O(n^2)
• Space Complexity: O(n)

3️⃣ Tabulation (Bottom-Up Approach)

Code:

int longestBitonicSubsequence(vector<int>& arr) {
    int n = arr.size();
    vector<int> lis(n, 1), lds(n, 1);

    // Compute LIS
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j])
                lis[i] = max(lis[i], lis[j] + 1);

    // Compute LDS
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j > i; j--)
            if (arr[i] > arr[j])
                lds[i] = max(lds[i], lds[j] + 1);

    // Combine both
    int maxLength = 0;
    for (int i = 0; i < n; i++)
        maxLength = max(maxLength, lis[i] + lds[i] - 1);

    return maxLength;
}

Complexity Analysis:

• Time Complexity: O(n^2)
• Space Complexity: O(n)