FastPrep
Problem · Dynamic Programming

Count Bitonic Subsequences

Learn this problem
● HardAtlassian logoAtlassianINTERNFULLTIMEOA

Problem statement

Count non-empty subsequences that strictly increase to an interior peak and then strictly decrease. Both the increasing and decreasing parts must contain at least one step. Return the count modulo 10^9 + 7.

Function

countBitonicSubsequences(arr: int[]) → int

Examples

Example 1

arr = [1,2,3,2,1]return = 11

Eleven index-distinct subsequences have a strict rise followed by a strict fall.

Example 2

arr = [1,2,3,1]return = 4

The valid subsequences are [1,2,1], [1,3,1], [2,3,1], and [1,2,3,1].

Constraints

  • 1 <= arr.length <= 100000
  • 1 <= arr[i] <= 200

More Atlassian problems

drafts saved locally
public int countBitonicSubsequences(int[] arr) {
  // Write your code here.
}
arr[1,2,3,2,1]
expected11
checking account