Given an array of positive integers. Find the maximum length of Bitonic subsequence. 
A subsequence of array is called Bitonic if it is first strictly increasing, then strictly decreasing.
 
Example 1:
Input: nums = [1, 2, 5, 3, 2]
Output: 5
Explanation: The sequence {1, 2, 5} is
increasing and the sequence {3, 2} is 
decreasing so merging both we will get 
length 5.
Example 2:
Input: nums = [1, 11, 2, 10, 4, 5, 2, 1]
Output: 6
Explanation: The bitonic sequence 
{1, 2, 10, 4, 2, 1} has length 6.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function LongestBitonicSequence() which takes the array nums[] as input parameter and returns the maximum length of bitonic subsequence.
 
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n)
 
Constraints:
1 ≤ length of array ≤ 10^{3}
1 ≤ arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def LongestBitonicSequence(self, nums):

		# Code here

Solutions:
class Solution:

	def LongestBitonicSequence(self, a):
		n = len(a)
		dp = [1] * n
		for ind in range(n):
			for prev in range(ind):
				if a[prev] < a[ind] and 1 + dp[prev] > dp[ind]:
					dp[ind] = 1 + dp[prev]
		maxi = 0
		dp2 = [1] * n
		for ind in range(n - 1, -1, -1):
			for prev in range(n - 1, ind, -1):
				if a[prev] < a[ind] and 1 + dp2[prev] > dp2[ind]:
					dp2[ind] = 1 + dp2[prev]
			maxi = max(maxi, dp[ind] + dp2[ind] - 1)
		return maxi


class Solution:

	def LongestBitonicSequence(self, nums):
		n = len(nums)
		dp1 = [1 for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if nums[i] > nums[j] and 1 + dp1[j] > dp1[i]:
					dp1[i] = 1 + dp1[j]
		dp2 = [1 for i in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, i, -1):
				if nums[i] > nums[j] and 1 + dp2[j] > dp2[i]:
					dp2[i] = 1 + dp2[j]
		maxi = 1
		for i in range(n):
			maxi = max(maxi, dp1[i] + dp2[i] - 1)
		return maxi


class Solution:

	def findLongestLeft(self, arr):
		dp = [1 for j in range(len(arr))]
		for i in range(len(arr)):
			for j in range(i):
				if arr[i] > arr[j] and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
		return dp

	def findLongestRight(self, arr):
		dp = [1 for j in range(len(arr))]
		for i in range(len(arr) - 2, -1, -1):
			for j in range(len(arr) - 1, i, -1):
				if arr[i] > arr[j] and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
		return dp

	def LongestBitonicSequence(self, nums):
		leftLCS = self.findLongestLeft(nums)
		rightLCS = self.findLongestRight(nums)
		ans = 0
		for i in range(len(leftLCS)):
			ans = max(ans, rightLCS[i] + leftLCS[i] - 1)
		return ans


class Solution:

	def removerecursiverepeatingelements(self, arr):
		i = 0
		while i < len(arr):
			while i + 1 < len(arr) and arr[i + 1] == arr[i]:
				arr.pop(i + 1)
			i += 1
		return arr

	def lis(self, arr):
		n = len(arr)
		lis = [1] * n
		for i in range(1, n):
			for j in range(0, i):
				if arr[i] > arr[j] and lis[i] < lis[j] + 1:
					lis[i] = lis[j] + 1
		return lis

	def LongestBitonicSequence(self, nums):
		nums = ob.removerecursiverepeatingelements(nums)
		li = ob.lis(nums)
		rev_li = ob.lis(nums[::-1])
		rev_li = rev_li[::-1]
		maxi = 0
		for i in range(len(li) + 1):
			if i == 0:
				a = 0
				b = max(rev_li[i:])
			elif i == len(li):
				a = max(li[:i])
				b = 0
			else:
				a = max(li[:i])
				b = max(rev_li[i:])
			maxi = max(maxi, a + b)
		return maxi


class Solution:

	def LongestBitonicSequence(self, nums):
		dp1 = [1 for i in range(len(nums))]
		for i in range(1, len(nums)):
			for j in range(i, -1, -1):
				if nums[i] > nums[j]:
					dp1[i] = max(dp1[i], dp1[j] + 1)
		dp2 = [1 for i in range(len(nums))]
		for i in range(len(nums) - 2, -1, -1):
			for j in range(i + 1, len(nums)):
				if nums[i] > nums[j]:
					dp2[i] = max(dp2[i], dp2[j] + 1)
		ans = 0
		for i in range(len(nums)):
			ans = max(ans, dp1[i] + dp2[i])
		return ans - 1