Given an array containing n numbers. The task is to find the maximum sum bitonic subarray. A bitonic subarray is a subarray in which elements are first increasing and then decreasing. A strictly increasing or strictly decreasing subarray is also considered as bitonic subarray.
 
Example 1:
Input:
n = 7
a[] = {5, 3, 9, 2, 7, 6, 4}
Output:
19
Explanation:
All Bitonic Subarrays are as follows:
{5}, {3}, {9}, {2}, {7}, {6}, {4},
{5,3}, {3,9}, {9,2}, {2,7}, {7,6}, 
{6,4}, {3,9,2}, {2,7,6}, {7,6,4}, {2,7,6,4}.
Out of these, the one with the maximum
sum is {2,7,6,4} whose sum is 19.
 
Example 2:
Input:
n = 7
a[] = {5, 4, 3, 2, 1, 10, 6}
Output:
17
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxSumBitonicSubArr() which takes the array a[] and its size n as inputs and returns the maximum bitonic subarray sum.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
 
Constraints:
1<=n<=10^{5}
1<=a[i]<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def maxSumBitonicSubArr(self, a, n):
        #Code here
    
    
    
    

Solutions:
class Solution:

	def maxSumBitonicSubArr(self, a, n):
		a[:] = map(int, a)
		(left, right) = ([0] * n, [0] * n)
		left[0] = a[0]
		for i in range(1, n):
			if a[i] > a[i - 1]:
				left[i] = left[i - 1] + a[i]
			else:
				left[i] = a[i]
		right[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			if a[i] > a[i + 1]:
				right[i] = right[i + 1] + a[i]
			else:
				right[i] = a[i]
		ans = 0
		for i in range(n):
			ans = max(left[i] + right[i] - a[i], ans)
		return ans


class Solution:

	def maxSumBitonicSubArr(self, arr, n):
		arr = list(map(int, arr))
		max_sum = -10 ** 9
		i = 0
		while i < n:
			j = i
			while j + 1 < n and arr[j] < arr[j + 1]:
				j += 1
			while i < j and arr[i] <= 0:
				i += 1
			k = j
			while k + 1 < n and arr[k] > arr[k + 1]:
				k += 1
			last = k
			while k > j and arr[k] <= 0:
				k -= 1
			nn = arr[i:j + 1]
			sum_inc = sum(nn)
			nn = arr[j:k + 1]
			sum_dec = sum(nn)
			sum_all = sum_inc + sum_dec - arr[j]
			max_sum = max([max_sum, sum_inc, sum_dec, sum_all])
			i = max(last, i + 1)
		return max_sum


class Solution:

	def maxSumBitonicSubArr(self, a, n):
		a = list(map(int, a))
		maxi = a[0]
		i = 0
		while i < n - 1:
			if a[i] == a[i + 1]:
				i += 1
			summa = a[i]
			while i < n - 1 and a[i] < a[i + 1]:
				i += 1
				summa += a[i]
			while i < n - 1 and a[i] > a[i + 1]:
				i += 1
				summa += a[i]
			maxi = max(maxi, summa)
		return maxi