DSA interview question

Longest Bitonic Subsequence

Medium · Algorithms · Topics: dynamic programming, lis

The problem

You're analyzing sensor data from a drone's altitude log during a single flight leg. A "clean" flight profile climbs to a peak altitude and then descends — this is called a bitonic pattern (strictly increasing, then strictly decreasing). Due to noise, the raw altitude readings aren't perfectly bitonic, but you want to find the longest subsequence of readings that does follow this climb-then-descend shape, to identify the cleanest usable segment of the flight for calibration purposes.

Given an integer array nums, find the length of the longest bitonic subsequence — a subsequence that is strictly increasing, then strictly decreasing (both parts non-empty is not required; a purely increasing or purely decreasing sequence also counts as bitonic).

Example: nums = [1,11,2,10,4,5,2,1] — the longest bitonic subsequence is [1,2,10,4,2,1] or [1,11,10,5,2,1], both of length 6.

Function signature

int longestBitonicSubsequence(vector<int>& nums);

Test cases

Input `nums`	Output	Explanation
`[1,11,2,10,4,5,2,1]`	6	e.g. `[1,2,10,4,2,1]`
`[12,11,40,5,3,1]`	5	Increasing part `[12,40]` (or `[11,40]`), then decreasing `[40,5,3,1]`
`[80,60,30,40,20,10]`	5	Purely decreasing after single peak: `[80,60,30,20,10]` or similar
`[1,2,3,4,5]`	5	Purely increasing — still valid bitonic
`[5,4,3,2,1]`	5	Purely decreasing — still valid bitonic
`[1]`	1	Single element
`[]`	0	Empty array

(Always confirm: strictly increasing/decreasing vs non-strict, and whether a monotonic array is a valid answer.)

How interviewers phrase it

"Find the length of the longest subsequence that first increases and then decreases."
"Given a mountain-shaped array pattern, find the longest such subsequence — it's fine if there's no decreasing part, or no increasing part."
Often introduced right after LIS as a natural extension: "Now that you've solved LIS, can you find the longest 'mountain' subsequence?"

Clarifying questions to ask

Does the sequence need both an increasing and a decreasing part, or is a purely increasing or purely decreasing array also considered bitonic? (This problem allows purely monotonic as valid.)
Should the increasing/decreasing be strict (no equal adjacent elements) or non-strict?
Can the peak be any single element, or must both sides around it have length ≥ 1? (Confirm: single-element and two-element arrays should still work.)
What's the expected size of nums? (Signals whether O(n²) is acceptable or O(n log n) is expected.)
Are duplicate values in the array possible?

Follow-ups to expect

"Can you also return the actual bitonic subsequence, not just its length?"
"Can you optimize to O(n log n)?"
"What if you need the longest bitonic subsequence where you must specify the peak index?"
"How is this different from 'Longest Mountain in Array' (contiguous subarray version)?"
"What if there could be multiple peaks (zigzag/alternating) — can you find the longest such pattern?"
"Can you do this with O(1) extra space?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview