Longest Bitonic Subsequence | LIS (DP 46)

A bitonic sequence is a sequence of numbers that first strictly increases and then strictly decreases, or follows a purely monotonic (increasing or decreasing) trend. By leveraging the foundational principles of the Longest Increasing Subsequence (LIS), we can decompose this problem into a forward increasing pass and a backward increasing pass.

1. Problem Statement & Definition of Bitonicity

A bitonic subsequence of an array is a sequence that satisfies the following criteria:

1. It first strictly increases up to a peak element.
2. It then strictly decreases from that peak element onwards.

Real-Life Analogy

Real-Life Analogy (Hiking a Mountain): Imagine walking along a mountain trail. You start at the base and hike strictly uphill until you reach the peak (increasing phase). Once at the top, you hike strictly downhill on the other side until you reach the foothills (decreasing phase). The Longest Bitonic Subsequence problem asks: What is the maximum number of checkpoints (elements) you can visit on such a hike?

Crucially, monotonic sequences are also valid bitonic subsequences:

• An array that only increases (e.g., [1, 2, 3, 4, 5, 6]) is a valid bitonic subsequence where the decreasing portion is of length zero.
• An array that only decreases (e.g., [5, 4, 3, 2, 1]) is a valid bitonic subsequence where the increasing portion is of length zero.

2. Why Do We Need This? (Limitations of Naive Search)

If we attempt to check all possible subsequences to find which ones rise and then fall, the time complexity explodes exponentially ($2^N$). Because subsequences exhibit optimal substructure and overlapping subproblems, we must rely on Dynamic Programming.

Specifically, we can reuse the engine of the Longest Increasing Subsequence (LIS). If we know the longest increasing subsequence ending at every index from the left, and the longest increasing subsequence starting at every index from the right (which is equivalent to an increasing subsequence from the reverse direction), we can combine them at every possible peak.

3. Core Mental Model: The Two-Pass Approach

To find the longest bitonic subsequence, we break the problem into two distinct DP tables:

1. dp1[i] (Forward LIS): Stores the length of the Longest Increasing Subsequence ending at index i (calculated from left to right).
2. dp2[i] (Backward LIS): Stores the length of the Longest Increasing Subsequence starting at index i (calculated from right to left).

When index i acts as the peak of our bitonic subsequence:

• dp1[i] gives the length of the increasing path leading up to and including i.
• dp2[i] gives the length of the increasing path starting from i and going backward (which represents the decreasing path in our original left-to-right view).
• Because element i is counted in both dp1[i] and dp2[i], we must subtract 1 to avoid double-counting it.

4. Step-by-Step Execution Flow

Let us trace the algorithm using an array, showing how the forward and backward passes combine.

Array: [1, 11, 2, 10, 4, 5, 2, 1]

Step 1: Compute Forward LIS (dp1) from index 0 to n-1
   dp1 values: [1, 2, 2, 3, 3, 4, 2, 1]
   
Step 2: Compute Backward LIS (dp2) from index n-1 to 0
   dp2 values: [1, 5, 2, 4, 3, 3, 2, 1]

Step 3: Combine at each potential peak i:
   Bitonic Length at index i = dp1[i] + dp2[i] - 1

Flow Walkthrough Example at Peak 10 (Index 3):

5. Complete C++ Implementation

Below is the production-ready C++ implementation combining forward LIS, backward LIS, and peak combination.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    int longestBitonicSubsequence(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        // dp1[i] stores LIS ending at index i (from left to right)
        vector<int> dp1(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int prev = 0; prev < i; ++prev) {
                if (nums[prev] < nums[i] && 1 + dp1[prev] > dp1[i]) {
                    dp1[i] = 1 + dp1[prev];
                }
            }
        }

        // dp2[i] stores LIS starting at index i (from right to left)
        vector<int> dp2(n, 1);
        for (int i = n - 1; i >= 0; --i) {
            for (int prev = n - 1; prev > i; --prev) {
                if (nums[prev] < nums[i] && 1 + dp2[prev] > dp2[i]) {
                    dp2[i] = 1 + dp2[prev];
                }
            }
        }

        // Find the maximum bitonic length by evaluating every index as a peak
        int maxBitonicLength = 0;
        for (int i = 0; i < n; ++i) {
            // Subtract 1 because nums[i] is included in both dp1[i] and dp2[i]
            int currentLength = dp1[i] + dp2[i] - 1;
            maxBitonicLength = max(maxBitonicLength, currentLength);
        }

        return maxBitonicLength;
    }
};

6. Complexity Analysis

Summary and Key Takeaways

• Bitonic Subsequence Definition: A sequence that strictly increases, reaches a peak, and then strictly decreases (monotonic increasing or decreasing sequences are also valid bitonic subsequences).
• Reduction to LIS: The problem is effectively solved by computing two separate Longest Increasing Subsequence (LIS) passes.
• Forward Pass (dp1): Computes the LIS ending at each index from left to right, capturing the "increasing" slope.
• Backward Pass (dp2): Computes the LIS starting at each index from right to left, capturing the "decreasing" slope when viewed forward.
• Peak Combination: For every index i, the peak bitonic length is given by dp1[i] + dp2[i] - 1.
• Deduplication: Always subtract 1 during combination because the peak element nums[i] is counted in both directional LIS calculations.
• Prerequisites: Mastery of DP 41 and DP 42 (LIS foundation) is essential for grasping the inner transition logic.