DSA Tracker

Visualize

Longest Bitonic Subsequence

answer = max(lis[i] + lds[i] - 1) — the peak counted once

time O(n^2)space O(n)

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.

Details

Animated on: nums = [12, 11, 40, 5, 3, 1] — find the length of the longest subsequence that strictly increases, then strictly decreases.

Problem:Longest Bitonic SubsequenceMedium

answer = max(lis[i] + lds[i] - 1) — the peak counted once

step 1 / 13

12 has nothing smaller before it, so the increasing run ending here is just itself: lis[0] = 1.

Pseudocode
1FUNCTION longestBitonic(nums):
2  n <- LENGTH(nums)
3  FOR i FROM 0 TO n-1:
4    lis[i] <- 1
5    FOR j FROM 0 TO i-1:
6      IF nums[j] < nums[i] AND lis[j]+1 > lis[i]:
7        lis[i] <- lis[j] + 1
8  FOR i FROM n-1 DOWNTO 0:
9    lds[i] <- 1
10    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] + 1
13  RETURN MAX(lis[i] + lds[i] - 1) FOR EACH i

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. 12 has nothing smaller before it, so the increasing run ending here is just itself: lis[0] = 1.
  2. 11 has nothing smaller before it, so the increasing run ending here is just itself: lis[1] = 1.
  3. 40 extends the run ending at 12 (lis[0] = 1), since 12 < 40: lis[2] = 2.
  4. 5 has nothing smaller before it, so the increasing run ending here is just itself: lis[3] = 1.
  5. 3 has nothing smaller before it, so the increasing run ending here is just itself: lis[4] = 1.
  6. 1 has nothing smaller before it, so the increasing run ending here is just itself: lis[5] = 1.
  7. 1 has nothing smaller after it, so the decreasing run starting here is just itself: lds[5] = 1.
  8. 3 leads into the run starting at 1 (lds[5] = 1), since 1 < 3: lds[4] = 2.
  9. 5 leads into the run starting at 3 (lds[4] = 2), since 3 < 5: lds[3] = 3.
  10. 40 leads into the run starting at 5 (lds[3] = 3), since 5 < 40: lds[2] = 4.
  11. 11 leads into the run starting at 5 (lds[3] = 3), since 5 < 11: lds[1] = 4.
  12. 12 leads into the run starting at 11 (lds[1] = 4), since 11 < 12: lds[0] = 5.
  13. 12 is the best peak: lis[0] = 1 increasing up to it, lds[0] = 5 decreasing away from it, shared once: 1 + 5 - 1 = 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Bitonic Subsequence in the editorAll Dynamic Programming problemsBack to roadmap