Skills101
← All coding problems

Longest Bitonic Subsequence

mediumDynamic Programming II+20 XPTime limit 2s

A trek's altitude readings are listed in order. A bitonic subsequence first goes strictly up and then strictly down — like climbing a hill and coming back. Either part may be empty, so a purely increasing or purely decreasing subsequence also counts. Find the length of the longest bitonic subsequence.

Input:

  • line 1: n
  • line 2: n integers

Output: the length of the longest bitonic subsequence.

Constraints: 1 ≤ n ≤ 2000, −10⁹ ≤ values ≤ 10⁹.

Example: in 1 11 2 10 4 5 2 1 one answer is 1 2 10 4 2 1 (length 6).

Think about it: for every index i, compute inc[i] = the longest strictly increasing subsequence ending at i, and dec[i] = the longest strictly decreasing subsequence starting at i (LIS from the right). The peak is some i: answer = max of inc[i] + dec[i] − 1.

Sample input 1

8
1 11 2 10 4 5 2 1

Sample output 1

6

Sample input 2

5
1 2 3 4 5

Sample output 2

5

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.