Given an array arr[] of N integers. A subsequence of arr[] is called Bitonic if it is first increasing then decreasing. Print the max sum bitonic subsequence.
Example 1:
Input :
N = 9
arr[] = {1, 15, 51, 45, 33,
                   100, 12, 18, 9}
Output : 194
Explanation :
Bi-tonic Sub-sequence are :
{1, 51, 9} or {1, 51, 100, 18, 9} or
{1, 15, 51, 100, 18, 9}  or
{1, 15, 45, 100, 12, 9}  or
{1, 15, 45, 100, 18, 9} .. so on           
Maximum sum Bi-tonic sub-sequence is 1 +
15 + 51 + 100 + 18 + 9 = 194
Example 2:
Input :
N = 6
arr[] = {80, 60, 30, 40, 20, 10}
Output :
210
Explanation :
Here the sequence is strinctly decreasing.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function leftIndex() which takes the array arr[] and its size N as inputs and returns the maximum Bitonic sequence sum.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1<=N<=10^{3}
1<=arr[]<=10^{5}

Difficulty: EASY
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



def maxSumBS( arr, n):

    return 0



Solutions:
def maxSumBS(s1, n):
	dp1 = [s1[i] for i in range(n)]
	for i in range(n):
		for j in range(i):
			if s1[i] > s1[j] and dp1[i] < dp1[j] + s1[i]:
				dp1[i] = s1[i] + dp1[j]
	dp2 = [s1[i] for i in range(n)]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, i, -1):
			if s1[i] > s1[j] and dp2[i] < dp2[j] + s1[i]:
				dp2[i] = s1[i] + dp2[j]
	maxi = float('-inf')
	for i in range(n):
		maxi = max(maxi, dp1[i] + dp2[i] - s1[i])
	return maxi


def maxSumBS(arr, n):
	maxinc = arr.copy()
	maxdec = [0 for i in range(n)]
	for i in range(n):
		for j in range(i):
			if arr[i] > arr[j]:
				maxinc[i] = max(maxinc[i], maxinc[j] + arr[i])
	for i in range(n - 1, -1, -1):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				maxdec[i] = max(maxdec[i], maxdec[j] + arr[j])
	res = -int(10000000000.0)
	for i in range(n):
		res = max(res, maxinc[i] + maxdec[i])
	return res


def maxSumBS(arr, n):
	inc = [0] * n
	dec = [0] * n
	inc[0] = arr[0]
	dec[n - 1] = arr[n - 1]
	for i in range(1, n):
		inc[i] = arr[i]
		for j in range(i):
			if arr[j] < arr[i]:
				inc[i] = max(inc[i], inc[j] + arr[i])
	for i in range(n - 2, -1, -1):
		dec[i] = arr[i]
		for j in range(n - 1, i, -1):
			if arr[j] < arr[i]:
				dec[i] = max(dec[i], dec[j] + arr[i])
	m = 0
	for i in range(n):
		m = max(m, inc[i] + dec[i] - arr[i])
	return m


def maxSumBS(arr, n):
	msibs = arr[:]
	for i in range(n):
		for j in range(0, i):
			if arr[i] > arr[j] and msibs[i] < msibs[j] + arr[i]:
				msibs[i] = msibs[j] + arr[i]
	msdbs = arr[:]
	for i in range(1, n + 1):
		for j in range(1, i):
			if arr[-i] > arr[-j] and msdbs[-i] < msdbs[-j] + arr[-i]:
				msdbs[-i] = msdbs[-j] + arr[-i]
	s = 0
	for i in range(n):
		s = max(s, msibs[i] + msdbs[i] - arr[i])
	return s


def maxSumBS(arr, n):

	def lis(arr):
		n = len(arr)
		lis = [0] * n
		for i in range(n):
			lis[i] = arr[i]
			temp = arr[i]
			for j in range(0, i):
				if arr[j] < arr[i]:
					temp = max(temp, arr[i] + lis[j])
			lis[i] = max(lis[i], temp)
		return lis

	def longest_decreasing_subsequence(arr):
		n = len(arr)
		lds = [0] * n
		for i in range(n - 1, -1, -1):
			lds[i] = arr[i]
			temp = arr[i]
			for j in range(n - 1, i, -1):
				if arr[j] < arr[i]:
					temp = max(temp, arr[i] + lds[j])
			lds[i] = max(lds[i], temp)
		return lds
	lis = lis(arr)
	lds = longest_decreasing_subsequence(arr)
	res = 0
	for i in range(n):
		res = max(res, lis[i] + lds[i] - arr[i])
	return res


def maxSumBS(arr, n):
	dpi = [0] * n
	dpd = [0] * n
	for i in range(n):
		for j in range(i - 1, -1, -1):
			if arr[j] < arr[i]:
				dpi[i] = max(dpi[i], dpi[j])
		dpi[i] += arr[i]
	for i in range(n - 1, -1, -1):
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				dpd[i] = max(dpd[i], dpd[j])
		dpd[i] += arr[i]
	ans = 0
	for i in range(n):
		ans = max(ans, dpi[i] + dpd[i] - arr[i])
	return ans


def maxSumBS(arr, n):
	l = arr[:]
	lis = arr[:]
	for i in range(1, n):
		for j in range(i):
			if arr[i] > arr[j] and lis[i] < lis[j] + arr[i]:
				lis[i] = arr[i] + lis[j]
	lds = arr[:]
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if arr[i] > arr[j] and lds[i] < lds[j] + arr[i]:
				lds[i] = lds[j] + arr[i]
	max1 = 1
	for i in range(n):
		max1 = max(max1, lis[i] + lds[i] - arr[i])
	return max1


def maxSumBS(arr, n):
	if n == 1:
		return arr[0]
	ldp = [0 for i in range(n)]
	rdp = [0 for i in range(n)]
	for i in range(n):
		ldp[i] = arr[i]
		mx = 0
		for j in range(i - 1, -1, -1):
			if arr[i] > arr[j]:
				mx = max(mx, ldp[j])
		ldp[i] += mx
	for i in range(n - 1, -1, -1):
		rdp[i] = arr[i]
		mx = 0
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				mx = max(mx, rdp[j])
		rdp[i] += mx
	ans = 0
	for i in range(n):
		x = ldp[i] + rdp[i] - arr[i]
		ans = max(ans, x)
	return ans


def maxSumBS(arr, n):
	MSIBS = arr[:]
	for i in range(n):
		for j in range(0, i):
			if arr[i] > arr[j] and MSIBS[i] < MSIBS[j] + arr[i]:
				MSIBS[i] = MSIBS[j] + arr[i]
	MSDBS = arr[:]
	for i in range(1, n + 1):
		for j in range(1, i):
			if arr[-i] > arr[-j] and MSDBS[-i] < MSDBS[-j] + arr[-i]:
				MSDBS[-i] = MSDBS[-j] + arr[-i]
	max_sum = float('-Inf')
	for (i, j, k) in zip(MSIBS, MSDBS, arr):
		max_sum = max(max_sum, i + j - k)
	return max_sum


def maxSumBS(a, n):
	incseq = list()
	decseq = list()
	for ele in a:
		incseq.append(ele)
		decseq.append(ele)
	for i in range(1, n):
		for j in range(i):
			if a[i] > a[j] and a[i] + incseq[j] > incseq[i]:
				incseq[i] = incseq[j] + a[i]
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if a[i] > a[j] and a[i] + decseq[j] > decseq[i]:
				decseq[i] = decseq[j] + a[i]
	merge = list()
	for i in range(n):
		merge.append(incseq[i] + decseq[i] - a[i])
	return max(merge)


def solve(arr, i, up, prev, dp):
	if i >= len(arr):
		return 0
	if (i, up, prev) in dp:
		return dp[i, up, prev]
	if up:
		if arr[i] > prev:
			dp[i, up, prev] = max(arr[i] + max(solve(arr, i + 1, True, arr[i], dp), solve(arr, i + 1, False, arr[i], dp)), solve(arr, i + 1, True, prev, dp), solve(arr, i + 1, False, prev, dp))
			return dp[i, up, prev]
		else:
			dp[i, up, prev] = max(solve(arr, i + 1, True, prev, dp), solve(arr, i + 1, False, prev, dp))
			return dp[i, up, prev]
	elif arr[i] < prev:
		dp[i, up, prev] = max(arr[i] + solve(arr, i + 1, False, arr[i], dp), solve(arr, i + 1, False, prev, dp))
		return dp[i, up, prev]
	else:
		dp[i, up, prev] = solve(arr, i + 1, False, prev, dp)
		return dp[i, up, prev]

def maxSumBS(arr, n):
	dp = {}
	return solve(arr, 0, True, -100000000, dp)


def maxSumBS(arr, n):
	MSIBS = arr[:]
	for i in range(n):
		for j in range(i):
			if arr[i] > arr[j]:
				MSIBS[i] = max(MSIBS[i], MSIBS[j] + arr[i])
	MSDBS = arr[:]
	for i in range(n - 1, -1, -1):
		for j in range(n - 1, i, -1):
			if arr[i] > arr[j]:
				MSDBS[i] = max(MSDBS[i], MSDBS[j] + arr[i])
	maxm = float('-inf')
	for (i, j, k) in zip(MSIBS, MSDBS, arr):
		maxm = max(maxm, i + j - k)
	return maxm


def maxSumBS(arr, n):
	max_sum = 0
	MIS = arr[:]
	for i in range(1, len(arr)):
		for j in range(i):
			if arr[i] > arr[j]:
				MIS[i] = max(MIS[i], arr[i] + MIS[j])
	MDS = arr[:]
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if arr[i] > arr[j]:
				MDS[i] = max(MDS[i], arr[i] + MDS[j])
	for i in range(n):
		max_sum = max(max_sum, MIS[i] + MDS[i] - arr[i])
	return max_sum


def maxSumBS(arr, n):
	g = [0] * n
	g[0] = arr[0]
	for i in range(n):
		x = 0
		for j in range(i):
			if arr[j] < arr[i]:
				x = max(x, g[j])
		g[i] = x + arr[i]
	s = [0] * n
	s[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		x = 0
		for j in range(n - 1, i, -1):
			if arr[j] < arr[i]:
				x = max(x, s[j])
		s[i] = x + arr[i]
	maxi = 0
	for i in range(n):
		maxi = max(s[i] + g[i] - arr[i], maxi)
	return maxi


def maxSumBS(arr, n):
	dp1 = [-1] * n
	maxi = 0
	for i in range(n):
		dp1[i] = arr[i]
		for j in range(0, i):
			if arr[j] < arr[i]:
				dp1[i] = max(dp1[i], arr[i] + dp1[j])
	dp2 = [-1] * n
	for i in range(n - 1, -1, -1):
		dp2[i] = arr[i]
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				dp2[i] = max(dp2[i], arr[i] + dp2[j])
	for i in range(n):
		if dp1[i] + dp2[i] - arr[i] > maxi:
			maxi = dp1[i] + dp2[i] - arr[i]
	return maxi


def maxSumBS(arr, n):
	l = [0] * n
	l[0] = arr[0]
	for i in range(1, n):
		m = 0
		for j in range(i):
			if arr[j] < arr[i]:
				m = max(m, l[j])
		l[i] = m + arr[i]
	r = [0] * n
	r[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		m = 0
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				m = max(m, r[j])
		r[i] = m + arr[i]
	m = 0
	for i in range(n):
		m = max(m, l[i] + r[i] - arr[i])
	return m


def maxSumBS(arr, n):
	l = [0] * n
	l[0] = arr[0]
	for i in range(1, n):
		m = 0
		for j in range(i):
			if arr[j] < arr[i]:
				m = max(m, l[j])
		l[i] = m + arr[i]
	r = [0] * n
	r[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		m = 0
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				m = max(m, r[j])
		r[i] = m + arr[i]
	m = 0
	for i in range(n):
		m = max(m, l[i] + r[i] - arr[i])
	return m

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(maxSumBS(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def maxSumBS(arr, n):
	left = [i for i in arr]
	for i in range(1, n):
		for j in range(i):
			if arr[i] > arr[j]:
				left[i] = max(left[i], arr[i] + left[j])
	right = [i for i in arr]
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if arr[i] > arr[j]:
				right[i] = max(right[i], arr[i] + right[j])
	ans = 0
	for i in range(n):
		ans = max(ans, left[i] + right[i] - arr[i])
	return ans


def maxSumBS(a, n):
	dp = [[0 for i in range(n)] for i in range(2)]
	dp[0][0] = a[0]
	dp[1][0] = a[0]
	for i in range(1, n):
		for j in range(0, i):
			if a[i] > a[j]:
				dp[0][i] = max(dp[0][i], dp[0][j] + a[i])
			elif a[i] < a[j]:
				dp[1][i] = max(dp[1][i], max(dp[1][j], dp[0][j]) + a[i])
			if dp[0][i] == 0:
				dp[0][i] = a[i]
			if dp[1][i] == 0:
				dp[1][i] = dp[0][i]
	return max(max(dp[0]), max(dp[1]))


def maxSumBS(arr, n):
	MISS = arr[:]
	for i in range(1, n):
		for j in range(0, i):
			if arr[j] < arr[i] and MISS[i] < MISS[j] + arr[i]:
				MISS[i] = MISS[j] + arr[i]
	MDSS = arr[:]
	for i in range(1, n + 1):
		for j in range(1, i):
			if arr[-j] < arr[-i] and MDSS[-i] < MDSS[-j] + arr[-i]:
				MDSS[-i] = MDSS[-j] + arr[-i]
	ans = arr[0]
	for (i, j, k) in zip(MISS, MDSS, arr):
		if i + j - k > ans:
			ans = i + j - k
	return ans


def maxSumBS(arr, n):
	X = arr
	n = len(X)
	DP = [1] * n
	DP1 = [1] * n
	DP2 = [0] * n
	summing1 = X[:]
	summing2 = X[:]
	summing3 = [0 for x in range(n)]
	for i in range(n):
		maximum = 1
		maximum1 = X[i]
		for j in range(i):
			if X[i] > X[j]:
				maximum = max(maximum, DP[j] + 1)
				maximum1 = max(maximum1, summing1[j] + summing1[i])
		DP[i] = maximum
		summing1[i] = maximum1
	for i in range(n - 1, -1, -1):
		maximum = 1
		maximum2 = X[i]
		for j in range(i, n):
			if X[i] > X[j]:
				maximum = max(maximum, DP1[j] + 1)
				maximum2 = max(maximum2, summing2[j] + summing2[i])
		DP1[i] = maximum
		summing2[i] = maximum2
	for i in range(n):
		DP2[i] = DP1[i] + DP[i]
		summing3[i] = summing1[i] + summing2[i] - X[i]
	return max(summing3)


def maxSumBS(arr, n):
	sum_increasing = [0 for i in range(n)]
	sum_decreasing = [0 for j in range(n)]
	for i in range(n):
		sum_increasing[i] = arr[i]
		for j in range(i):
			if arr[j] < arr[i]:
				sum_increasing[i] = max(sum_increasing[i], sum_increasing[j] + arr[i])
	for i in range(n - 1, -1, -1):
		sum_decreasing[i] = arr[i]
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				sum_decreasing[i] = max(sum_decreasing[i], sum_decreasing[j] + arr[i])
	ans = 0
	for i in range(0, n):
		ans = max(ans, sum_increasing[i] + sum_decreasing[i] - arr[i])
	return ans


def maxSumBS(arr, n):
	left_lis = [i for i in arr]
	for i in range(1, n):
		for j in range(i):
			if arr[i] > arr[j]:
				left_lis[i] = max(left_lis[i], arr[i] + left_lis[j])
	right_lis = [arr[i] for i in range(n - 1, -1, -1)]
	right_arr = [i for i in right_lis]
	for i in range(1, n):
		for j in range(i):
			if right_arr[i] > right_arr[j]:
				right_lis[i] = max(right_lis[i], right_arr[i] + right_lis[j])
	ans = 0
	for i in range(n):
		ans = max(ans, left_lis[i] + right_lis[n - i - 1] - arr[i])
	return ans


def maxSumBS(arr, n):
	si = arr[:]
	sd = arr[:]
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and si[j] + arr[i] > si[i]:
				si[i] = si[j] + arr[i]
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i - 1, -1):
			if arr[i] > arr[j] and sd[j] + arr[i] > sd[i]:
				sd[i] = sd[j] + arr[i]
	res = sd[0] + si[0] - arr[0]
	for i in range(1, n):
		res = max(res, sd[i] + si[i] - arr[i])
	return res


def maxSumBS(arr, n):
	dp = [[0 for i in range(2)] for j in range(n)]
	if n == 1:
		return arr[0]
	dp[0][0] = arr[0]
	for i in range(1, n):
		for j in range(i):
			if arr[j] < arr[i] and dp[i][0] < dp[j][0]:
				dp[i][0] = max(dp[i][0], dp[j][0])
		dp[i][0] += arr[i]
	dp[n - 1][1] = arr[n - 1]
	m = 0
	for i in range(n - 2, -1, -1):
		for j in range(i + 1, n):
			if arr[i] > arr[j] and dp[i][1] < dp[j][1]:
				dp[i][1] = max(dp[i][1], dp[j][1])
		dp[i][1] += arr[i]
	for i in range(n):
		m = max(m, dp[i][0] + dp[i][1] - arr[i])
	return m


def maxSumBS(arr, n):
	max_sum = arr[0]
	MSIBS = []
	MSDBS = []
	for i in arr:
		MSDBS.append(i)
		MSIBS.append(i)
	for i in range(1, n):
		for j in range(i):
			if arr[i] > arr[j] and MSIBS[i] < MSIBS[j] + arr[i]:
				MSIBS[i] = MSIBS[j] + arr[i]
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, i, -1):
			if arr[i] > arr[j] and MSDBS[i] < MSDBS[j] + arr[i]:
				MSDBS[i] = MSDBS[j] + arr[i]
	for i in range(n):
		max_sum = max(max_sum, MSDBS[i] + MSIBS[i] - arr[i])
	return max_sum


def maxSumBS(arr, n):
	if True:
		lis = [1] * len(arr)
		lds = [1] * len(arr)
		n = len(arr)
		for i in range(n):
			lis[i] = arr[i]
			for j in range(i):
				if arr[j] < arr[i]:
					lis[i] = max(lis[i], lis[j] + arr[i])
		for i in range(n - 1, -1, -1):
			lds[i] = arr[i]
			for j in range(n - 1, i, -1):
				if arr[j] < arr[i]:
					lds[i] = max(lds[i], lds[j] + arr[i])
		ans = -1000
		ann = 0
		for i in range(n):
			if ans <= lis[i] + lds[i] - arr[i]:
				ans = lis[i] + lds[i] - arr[i]
				ann = i
		return ans


def maxSumBS(nums, n):
	dp1 = nums[:]
	for ind in range(0, n):
		for prev in range(0, ind):
			if nums[prev] < nums[ind]:
				dp1[ind] = max(dp1[ind], nums[ind] + dp1[prev])
	dp2 = nums[:]
	for ind in range(n - 1, -1, -1):
		for prev in range(n - 1, ind, -1):
			if nums[prev] < nums[ind]:
				dp2[ind] = max(dp2[ind], nums[ind] + dp2[prev])
	bitonic = []
	index = 0
	for (i, j) in zip(dp1, dp2):
		bitonic.append(i + j - nums[index])
		index += 1
	return max(bitonic)


def maxSumBS(l, n):
	dp1 = [0 for _ in range(n)]
	dp1[0] = l[0]
	for i in range(1, n):
		for j in range(0, i):
			if l[i] > l[j]:
				dp1[i] = max(dp1[i], dp1[j] + l[i])
			else:
				dp1[i] = max(dp1[i], l[i])
	dp2 = [0 for _ in range(n)]
	dp2[-1] = l[-1]
	for i in range(n - 2, -1, -1):
		for j in range(i + 1, n):
			if l[i] > l[j]:
				dp2[i] = max(dp2[i], dp2[j] + l[i])
			else:
				dp2[i] = max(l[i], dp2[i])
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if l[i] != l[j]:
				ans = max(ans, dp1[i] + dp2[j])
	return max(ans, max(l))


def maxSumBS(arr, n):
	ib = arr[:]
	for i in range(n):
		for j in range(0, i):
			if arr[i] > arr[j] and ib[i] < ib[j] + arr[i]:
				ib[i] = ib[j] + arr[i]
	db = arr[:]
	for i in range(1, n + 1):
		for j in range(1, i):
			if arr[-i] > arr[-j] and db[-i] < db[-j] + arr[-i]:
				db[-i] = db[-j] + arr[-i]
	max_sum = float('-Inf')
	for (i, j, k) in zip(ib, db, arr):
		max_sum = max(max_sum, i + j - k)
	return max_sum


def maxSumBS(niz, n):
	suma_raste = [niz[i] for i in range(n)]
	suma_opada = [0 for _ in range(n)]
	for i in range(1, n):
		tmax = 0
		for j in range(i):
			if niz[i] > niz[j]:
				if suma_raste[j] > tmax:
					tmax = suma_raste[j]
		suma_raste[i] = tmax + niz[i]
		tmax = 0
		for j in range(i):
			if niz[i] < niz[j]:
				t = max(suma_opada[j], suma_raste[j])
				if t + niz[i] > tmax:
					tmax = t + niz[i]
		suma_opada[i] = tmax
	return max(max(suma_raste), max(suma_opada))


def maxSumBS(arr, _):
	sum_dec = max_sum_inc(arr[::-1])[::-1]
	sum_inc = max_sum_inc(arr)
	return max((sum_inc[i] + sum_dec[i] - arr[i] for i in range(len(arr))))

def max_sum_inc(arr):
	sum_inc = arr.copy()
	for i in range(1, len(arr)):
		for j in range(i):
			if arr[i] > arr[j] and sum_inc[i] < arr[i] + sum_inc[j]:
				sum_inc[i] = sum_inc[j] + arr[i]
	return sum_inc


def LIS(arr, n):
	dp = arr.copy()
	for i in range(1, n):
		for j in range(i):
			if arr[j] < arr[i]:
				dp[i] = max(dp[i], dp[j] + arr[i])
	return dp

def LDS(arr, n):
	dp = arr.copy()
	for i in range(n - 2, -1, -1):
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				dp[i] = max(dp[i], dp[j] + arr[i])
	return dp

def maxSumBS(arr, n):
	lis = LIS(arr, n)
	lds = LDS(arr, n)
	ans = 0
	for i in range(n):
		ans = max(ans, lis[i] + lds[i] - arr[i])
	return ans