Pattern visualizer
Longest Bitonic Subsequence
A bitonic subsequence has one peak element: everything before it strictly increases, everything after it strictly decreases. So for every index i, ask two separate questions — how long is the longest increasing run ending at i, and how long is the longest decreasing run starting at i — and answer both with an ordinary LIS-style sweep, once left to right and once right to left. Adding the two counts at any i and subtracting 1 (i itself is counted in both) gives the longest bitonic subsequence with i as its peak, so the overall answer is just the best peak. Animated on: nums = [12, 11, 40, 5, 3, 1] — find the length of the longest subsequence that strictly increases, then strictly decreases..
answer = max(lis[i] + lds[i] - 1) — the peak counted once
12 has nothing smaller before it, so the increasing run ending here is just itself: lis[0] = 1.
1FUNCTION longestBitonic(nums):2 n <- LENGTH(nums)3 FOR i FROM 0 TO n-1:4 lis[i] <- 15 FOR j FROM 0 TO i-1:6 IF nums[j] < nums[i] AND lis[j]+1 > lis[i]:7 lis[i] <- lis[j] + 18 FOR i FROM n-1 DOWNTO 0:9 lds[i] <- 110 FOR j FROM i+1 TO n-1:11 IF nums[j] < nums[i] AND lds[j]+1 > lds[i]:12 lds[i] <- lds[j] + 113 RETURN MAX(lis[i] + lds[i] - 1) FOR EACH i
← / → step · space play · Home restart