Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- MOD = 10**9 + 7
- def countBitonicSubsequences(arr):
- n = len(arr)
- increasing = [0] * n
- decreasing = [0] * n
- # Count increasing subsequences
- for i in range(n):
- for j in range(i):
- if arr[j] < arr[i]:
- increasing[i] = (increasing[i] + increasing[j] + 1) % MOD
- # Count decreasing subsequences
- for i in reversed(range(n)):
- for j in range(i+1, n):
- if arr[j] < arr[i]:
- decreasing[i] = (decreasing[i] + decreasing[j] + 1) % MOD
- # Count bitonic subsequences
- count = 0
- for i in range(1, n-1):
- count = (count + increasing[i] * decreasing[i]) % MOD
- return count
- # Test the function with the given example
- arr = [100,50,50,100]
- print(countBitonicSubsequences(arr))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement