Longest Bitonic Subsequence

Problem

Return the length of the longest subsequence of arr that first strictly increases and then strictly decreases; a purely increasing or purely decreasing run also counts.

Compute increasing lengths from the left and decreasing lengths from the right, then maximise inc[i] + dec[i] - 1 over every center. Return 0 for an empty list.

Hint

The peak element is counted in both tables, so subtract 1.

Test cases

case 1

in: [[1,11,2,10,4,5,2,1]]

expected: 6

case 2

in: [[1,2,3,4,5]]

expected: 5

case 3

in: [[5,4,3,2,1]]

expected: 5

case 4

in: [[1,2,3,2,1]]

expected: 5

case 5

in: [[]]

expected: 0

case 6

in: [[1]]

expected: 1

Starter codePython

def longest_bitonic_subsequence(arr):
    # Your code here
    pass

6 test cases · run your code against them in the editor