Log inSign up
mediumGeeksforGeeksNot Started

Longest Bitonic Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

A sequence is called bitonic if it is first strictly increasing, and then strictly decreasing. Alternatively, a sequence can be entirely strictly increasing or entirely strictly decreasing.

Given an array of positive integers nums, return the length of the longest bitonic subsequence.

### Example 1 - Input: nums = [1, 2, 5, 3, 2] - Output: 5 - Explanation: The entire sequence [1, 2, 5, 3, 2] is bitonic (increases from 1 to 5, then decreases from 5 to 2).

### Example 2 - Input: nums = [1, 11, 2, 10, 4, 5, 2, 1] - Output: 6 - Explanation: The subsequence [1, 2, 10, 4, 2, 1] or [1, 2, 10, 5, 2, 1] has length 6.

### Example 3 - Input: nums = [10, 20, 30] - Output: 3 - Explanation: Strictly increasing is also considered bitonic.

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine forward and backward DP scans into a composite peak pattern.
  • Understand why peak i is shared between LIS and LDS.
  • Formulate the O(n2) DP solution and understand the O(n log n) extension.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sequence that increases to a peak then decreases.
  • Subsequence problem asking for maximum combined length.

Algorithmic Decision Tree:

  • Compute prefix LIS and suffix LDS independently.
  • Aggregate at each element as peak.

Connected Patterns:

Longest Increasing SubsequenceMaximum Subarray SumTrapping Rain Water

1. All Peaks Enumeration with Subsequence Search

Intuition

For each index i, recursively search for the longest increasing subsequence ending at i and longest decreasing starting at i.

Algorithm

  1. For each index i from 0 to n-1:
  2. Find max increasing subsequence ending at i.
  3. Find max decreasing subsequence starting at i.
  4. Add lengths and subtract 1.
  5. Return global maximum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int getLIS(int idx, const vector<int>& nums) {
8 int maxLen = 1;
9 for (int j = 0; j < idx; j++) {
10 if (nums[j] < nums[idx]) {
11 maxLen = max(maxLen, 1 + getLIS(j, nums));
12 }
13 }
14 return maxLen;
15}
16
17int getLDS(int idx, const vector<int>& nums) {
18 int maxLen = 1;
19 for (int j = idx + 1; j < (int)nums.size(); j++) {
20 if (nums[j] < nums[idx]) {
21 maxLen = max(maxLen, 1 + getLDS(j, nums));
22 }
23 }
24 return maxLen;
25}
26
27int longestBitonicRec(const vector<int>& nums) {
28 int n = nums.size();
29 int ans = 0;
30 for (int i = 0; i < n; i++) {
31 ans = max(ans, getLIS(i, nums) + getLDS(i, nums) - 1);
32 }
33 return ans;
34}
35
36int main() {
37 vector<int> nums = {1, 2, 5, 3, 2};
38 cout << "Longest Bitonic (Recursive): " << longestBitonicRec(nums) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(n * 2^n)
  • Space complexity: O(n) call stack

2. Bidirectional DP Arrays (LIS + LDS)

Intuition

Compute array lis from left to right and array lds from right to left in O(n2) total time.

Algorithm

  1. Initialize lis and lds of size n filled with 1.
  2. Left-to-right: for i = 0 to n - 1: for j = 0 to i - 1: if nums[j] < nums[i]: lis[i] = max(lis[i], 1 + lis[j]).
  3. Right-to-left: for i = n - 1 down to 0: for j = n - 1 down to i + 1: if nums[j] < nums[i]: lds[i] = max(lds[i], 1 + lds[j]).
  4. Find maximum of lis[i] + lds[i] - 1 over all i.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int longestBitonicDP(const vector<int>& nums) {
8 int n = nums.size();
9 if (n <= 1) return n;
10
11 vector<int> lis(n, 1);
12 for (int i = 0; i < n; i++) {
13 for (int j = 0; j < i; j++) {
14 if (nums[j] < nums[i]) {
15 lis[i] = max(lis[i], 1 + lis[j]);
16 }
17 }
18 }
19
20 vector<int> lds(n, 1);
21 for (int i = n - 1; i >= 0; i--) {
22 for (int j = n - 1; j > i; j--) {
23 if (nums[j] < nums[i]) {
24 lds[i] = max(lds[i], 1 + lds[j]);
25 }
26 }
27 }
28
29 int maxLen = 0;
30 for (int i = 0; i < n; i++) {
31 maxLen = max(maxLen, lis[i] + lds[i] - 1);
32 }
33 return maxLen;
34}
35
36int main() {
37 vector<int> nums = {1, 2, 5, 3, 2};
38 cout << "Longest Bitonic (2-Pass DP): " << longestBitonicDP(nums) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n) for lis and lds arrays

3. Binary Search Patience Sorting LIS + LDS O(n log n)

Intuition

Accelerate both the forward LIS and backward LDS computations to O(n log n) using binary search (lower_bound).

Algorithm

  1. For forward LIS: maintain tails array. For each element nums[i], binary search its insertion point. lis[i] = insertion_index + 1.
  2. For backward LDS: maintain tails array on reversed array. lds[i] = insertion_index + 1.
  3. Compute max(lis[i] + lds[i] - 1) across all i.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int longestBitonicOptimal(const vector<int>& nums) {
8 int n = nums.size();
9 if (n <= 1) return n;
10
11 vector<int> lis(n, 1);
12 vector<int> tails;
13 for (int i = 0; i < n; i++) {
14 auto it = lower_bound(tails.begin(), tails.end(), nums[i]);
15 int idx = it - tails.begin();
16 if (it == tails.end()) tails.push_back(nums[i]);
17 else *it = nums[i];
18 lis[i] = idx + 1;
19 }
20
21 vector<int> lds(n, 1);
22 tails.clear();
23 for (int i = n - 1; i >= 0; i--) {
24 auto it = lower_bound(tails.begin(), tails.end(), nums[i]);
25 int idx = it - tails.begin();
26 if (it == tails.end()) tails.push_back(nums[i]);
27 else *it = nums[i];
28 lds[i] = idx + 1;
29 }
30
31 int maxLen = 0;
32 for (int i = 0; i < n; i++) {
33 maxLen = max(maxLen, lis[i] + lds[i] - 1);
34 }
35 return maxLen;
36}
37
38int main() {
39 vector<int> nums = {1, 2, 5, 3, 2};
40 cout << "Longest Bitonic (Optimal O(n log n)): " << longestBitonicOptimal(nums) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(n) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Peaks RecursionO(n * 2^n)O(n)Exhaustive recursive search for every candidate peak.Redundant subsequences
2.2-Pass DP (lis + lds)O(n^2)O(n)Quadratic LIS and LDS table construction.Nested comparison loop
3.Patience Sorting O(n log n)OptimalO(n log n)O(n)Binary search on tails array for both directions.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to subtract 1 from lis[i] + lds[i].

Pitfall 2:

Running LDS from left to right instead of right to left.

Crucial Edge Cases to Validate:

  • Monotonically increasing: LDS is 1 for all elements, output equals LIS.
  • Monotonically decreasing: LIS is 1 for all elements, output equals LDS.
  • Single element: Output is 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the O(n2) solution first to make the logic completely clear, then offer to optimize it to O(n log n) using patience sorting/binary search.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we subtract 1 in the formula lis[i] + lds[i] - 1 when calculating bitonic length around peak i?

Back to DSA Sheet