The longest rise-then-fall subsequence
A sequence is bitonic if it strictly increases and then strictly decreases (either part may be empty). Given
nums, return the length of its longest bitonic subsequence.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1,11,2,10,4,5,2,1] | 6 | 1, 2, 10, 4, 2, 1. |
nums = [12,11,40,5,3,1] | 5 | 12, 40, 5, 3, 1. |
nums = [80,60,30,40,20,10] | 5 | 80, 60, 40, 20, 10: no rise at all. |
Constraints
- 1 ≤ nums.length ≤ 2000
- −10⁶ ≤ nums[i] ≤ 10⁶
Hints
Hint 1
A bitonic subsequence has a peak. Fix the peak position i.
Hint 2
up[i] = longest increasing subsequence ending at i (from the left); down[i] = longest decreasing subsequence starting at i (an increasing one from the right).
Hint 3
The answer is the maximum of up[i] + down[i] − 1.
Where people lose marks
- Forgetting the − 1 for the shared peak.
- Requiring both parts to be non-empty when the problem allows a purely increasing or decreasing sequence.
Dry run on [1,11,2,10,4,5,2,1]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 3nums101112210344552617up1021223334452617
Left to right: the longest increasing subsequence ending at each position.
-
Step 2 / 3nums101112210344552617up1021223334452617down1051224334352617
Right to left: the longest decreasing subsequence starting at each position.
-
Step 3 / 3nums101112210344552617up + down − 11061326354653617
The best peak is 11 at position 1: 2 + 5 − 1 = 6.
How to think about it
Every bitonic subsequence has a peak, its largest element. Fix the peak at position i: the best rise into it is the
longest increasing subsequence ending at i, and the best fall out of it is the longest decreasing subsequence starting at
i, which is an increasing subsequence computed from the right. Compute both tables with the LIS recurrence and take the
best up[i] + down[i] − 1 (the peak is counted twice).
Complexity. Time O(n²) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def longest_bitonic(nums):
n = len(nums)
up = [1] * n # longest increasing subsequence ending at i
down = [1] * n # longest decreasing subsequence starting at i
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
up[i] = max(up[i], up[j] + 1)
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
if nums[j] < nums[i]:
down[i] = max(down[i], down[j] + 1)
return max(u + d - 1 for u, d in zip(up, down)) # the peak is counted twice#include <algorithm>
#include <vector>
int solve(const std::vector<int>& nums) {
const int n = nums.size();
std::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] = std::max(up[i], up[j] + 1);
for (int i = n - 1; i >= 0; --i)
for (int j = n - 1; j > i; --j) if (nums[j] < nums[i]) down[i] = std::max(down[i], down[j] + 1);
int best = 0;
for (int i = 0; i < n; ++i) best = std::max(best, up[i] + down[i] - 1); // shared peak
return best;
}class Solution {
public int longestBitonic(int[] nums) {
int n = nums.length, best = 0;
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 = n - 1; j > i; j--) if (nums[j] < nums[i]) down[i] = Math.max(down[i], down[j] + 1); }
for (int i = 0; i < n; i++) best = Math.max(best, up[i] + down[i] - 1); // shared peak
return best;
}
}function longestBitonic(nums) {
const n = nums.length, up = new Array(n).fill(1), down = new Array(n).fill(1);
for (let i = 0; i < n; i++) for (let j = 0; j < i; j++) if (nums[j] < nums[i]) up[i] = Math.max(up[i], up[j] + 1);
for (let i = n - 1; i >= 0; i--) for (let j = n - 1; j > i; j--) if (nums[j] < nums[i]) down[i] = Math.max(down[i], down[j] + 1);
let best = 0;
for (let i = 0; i < n; i++) best = Math.max(best, up[i] + down[i] - 1); // shared peak
return best;
}fn solve(nums: &[i64]) -> i64 {
let n = nums.len();
let (mut up, mut down) = (vec![1i64; n], vec![1i64; n]);
for i in 0..n {
for j in 0..i {
if nums[j] < nums[i] {
up[i] = up[i].max(up[j] + 1);
}
}
}
for i in (0..n).rev() {
for j in i + 1..n {
if nums[j] < nums[i] {
down[i] = down[i].max(down[j] + 1);
}
}
}
(0..n).map(|i| up[i] + down[i] - 1).max().unwrap() // shared peak
}import Data.Array
solve :: [Int] -> Int
solve nums = maximum [up ! i + down ! i - 1 | i <- [0 .. n - 1]] -- the peak is counted twice
where
n = length nums
a = listArray (0, n - 1) nums
up = listArray (0, n - 1) [1 + maximum (0 : [up ! j | j <- [0 .. i - 1], a ! j < a ! i]) | i <- [0 .. n - 1]] :: Array Int Int
down = listArray (0, n - 1) [1 + maximum (0 : [down ! j | j <- [i + 1 .. n - 1], a ! j < a ! i]) | i <- [0 .. n - 1]] :: Array Int IntVariants to try
- O(n log n) by running the patience-sorting LIS from both sides.
- Return the subsequence itself.
- Allow equal neighbours at the peak (non-strict).
Next problems
The largest chain of divisors
Find the size of the largest subset of distinct positive integers in which every pair divides one way or the other. Sort first, and divisibility becomes a chain.
Open the problem → Medium25 minHow many longest increasing subsequences
Count the strictly increasing subsequences of maximum length. Keep, for each position, the best length ending there and how many subsequences achieve it.
Open the problem → Medium20 minThe longest alternating subsequence
Return the length of the longest subsequence whose successive differences alternate between positive and negative. Two numbers carry the whole table.
Open the problem →Write a solution and run it against the real test table.
Keep going
The largest chain of divisors
Find the size of the largest subset of distinct positive integers in which every pair divides one way or the other. Sort first, and divisibility becomes a chain.
Open the problem → Medium25 minHow many longest increasing subsequences
Count the strictly increasing subsequences of maximum length. Keep, for each position, the best length ending there and how many subsequences achieve it.
Open the problem → Medium20 minThe longest alternating subsequence
Return the length of the longest subsequence whose successive differences alternate between positive and negative. Two numbers carry the whole table.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.