Longest Bitonic Subsequence — Solution in Python, Java & C++
Longest Bitonic Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Bitonic Subsequence is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sequence is bitonic if it first strictly increases and then strictly decreases, and both parts are non-empty — that is, it rises to a single peak and then falls, like 1, 4, 6, 3, 2. A sequence that only increases, or only decreases, is not bitonic.
Given an array nums, return the length of its longest bitonic subsequence (elements kept in their original order, not necessarily adjacent). If no bitonic subsequence exists, return 0.
Example 1
Input: nums = [1,2,5,3,2]
Output: 5
Explanation: The whole array rises 1, 2, 5 and falls 5, 3, 2.
Example 2
Input: nums = [1,11,2,10,4,5,2,1]
Output: 6
Explanation: One longest choice is 1, 2, 10, 4, 2, 1.
Example 3
Input: nums = [10,20,30]
Output: 0
Explanation: The array only increases, so no subsequence can fall after its peak.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^4
Hints for Longest Bitonic Subsequence
Hint 1
Every bitonic subsequence has a peak element. To its left is a strictly increasing subsequence ending at the peak, to its right a strictly decreasing one starting at it.
Hint 2
Compute, for each index
i, the longest strictly increasing subsequence ending ati(up[i]) and the longest strictly decreasing subsequence starting ati(down[i]).Hint 3
The best bitonic subsequence with peak
ihas lengthup[i] + down[i] - 1— but only count peaks whereup[i] > 1anddown[i] > 1, so both sides are non-empty.
How to solve Longest Bitonic Subsequence
Split a bitonic subsequence at its peak. The rising half is any increasing subsequence ending at the peak and the falling half any decreasing subsequence starting there; the two halves only share the peak, so they can be optimised independently — two LIS computations, one from each side.
Approach
up[i]= 1 + maxup[j]overj < iwithnums[j] < nums[i](1 if none).down[i]= 1 + maxdown[j]overj > iwithnums[j] < nums[i](1 if none), filled from the right.- Answer = max of
up[i] + down[i] - 1over alliwithup[i] >= 2anddown[i] >= 2;0if there is no suchi.
Why it works
For a fixed peak i, any increasing subsequence ending at i and any decreasing subsequence starting at i concatenate (sharing i) into a valid bitonic subsequence, because every element on the left is before i and smaller than nums[i], and every element on the right is after i and smaller too. Maximising each half separately therefore maximises the total for that peak, and the best peak gives the answer.
Complexity
- Time —
O(n^2) (O(n log n) with patience sorting for both halves) - Space —
O(n)
Pitfalls
- Both halves must be non-empty: a purely increasing or decreasing array answers
0, not its length. - Strictly: equal neighbours cannot both be in one half — use
<, not<=. - The peak is counted in both
upanddown, hence the- 1.
Reference solution
Python
from typing import List
def longestBitonicSequence(nums: List[int]) -> int:
n = len(nums)
up = [1] * n
down = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i] and up[j] + 1 > up[i]:
up[i] = up[j] + 1
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if nums[j] < nums[i] and down[j] + 1 > down[i]:
down[i] = down[j] + 1
best = 0
for i in range(n):
if up[i] > 1 and down[i] > 1:
best = max(best, up[i] + down[i] - 1)
return bestJava
public static int longestBitonicSequence(int[] nums) {
int n = nums.length;
int[] up = new int[n], down = new int[n];
for (int i = 0; i < n; i++) {
up[i] = 1;
for (int j = 0; j < i; j++) if (nums[j] < nums[i]) up[i] = Math.max(up[i], up[j] + 1);
}
for (int i = n - 1; i >= 0; i--) {
down[i] = 1;
for (int j = i + 1; j < n; j++) if (nums[j] < nums[i]) down[i] = Math.max(down[i], down[j] + 1);
}
int best = 0;
for (int i = 0; i < n; i++) {
if (up[i] > 1 && down[i] > 1) best = Math.max(best, up[i] + down[i] - 1);
}
return best;
}C++
int longestBitonicSequence(vector<int>& nums) {
int n = nums.size();
vector<int> up(n, 1), down(n, 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) up[i] = max(up[i], up[j] + 1);
for (int i = n - 1; i >= 0; i--)
for (int j = i + 1; j < n; j++)
if (nums[j] < nums[i]) down[i] = max(down[i], down[j] + 1);
int best = 0;
for (int i = 0; i < n; i++)
if (up[i] > 1 && down[i] > 1) best = max(best, up[i] + down[i] - 1);
return best;
}JavaScript
var longestBitonicSequence = function(nums) {
var n = nums.length;
var up = new Array(n).fill(1), down = new Array(n).fill(1);
for (var i = 0; i < n; i++) {
for (var j = 0; j < i; j++) if (nums[j] < nums[i] && up[j] + 1 > up[i]) up[i] = up[j] + 1;
}
for (var a = n - 1; a >= 0; a--) {
for (var b = a + 1; b < n; b++) if (nums[b] < nums[a] && down[b] + 1 > down[a]) down[a] = down[b] + 1;
}
var best = 0;
for (var k = 0; k < n; k++) {
if (up[k] > 1 && down[k] > 1 && up[k] + down[k] - 1 > best) best = up[k] + down[k] - 1;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming