Advertisement
rajeshinternshala

Untitled

Jan 13th, 2024
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.79 KB | None | 0 0
  1. MOD = 10**9 + 7
  2.  
  3. def countBitonicSubsequences(arr):
  4.     n = len(arr)
  5.     increasing = [0] * n
  6.     decreasing = [0] * n
  7.  
  8.     # Count increasing subsequences
  9.     for i in range(n):
  10.         for j in range(i):
  11.             if arr[j] < arr[i]:
  12.                 increasing[i] = (increasing[i] + increasing[j] + 1) % MOD
  13.  
  14.     # Count decreasing subsequences
  15.     for i in reversed(range(n)):
  16.         for j in range(i+1, n):
  17.             if arr[j] < arr[i]:
  18.                 decreasing[i] = (decreasing[i] + decreasing[j] + 1) % MOD
  19.  
  20.     # Count bitonic subsequences
  21.     count = 0
  22.     for i in range(1, n-1):
  23.         count = (count + increasing[i] * decreasing[i]) % MOD
  24.  
  25.     return count
  26.  
  27. # Test the function with the given example
  28. arr = [100,50,50,100]
  29. print(countBitonicSubsequences(arr))
  30.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement