Question: 
Write a function to find the maximum sum of bi-tonic sub-sequence for the given array.


Model's Code:
def max_sum(arr, n):
    if n == 0:
        return 0

    increasing = [0] * n
    decreasing = [0] * n

    for i in range(n):
        increasing[i] = arr[i]
        for j in range(i):
            if arr[i] > arr[j]:
                increasing[i] = max(increasing[i], increasing[j] + arr[i])

    for i in range(n-1, -1, -1):
        decreasing[i] = arr[i]
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                decreasing[i] = max(decreasing[i], decreasing[j] + arr[i])

    max_bi_tonic_sum = 0
    for i in range(n):
        max_bi_tonic_sum = max(max_bi_tonic_sum, increasing[i] + decreasing[i] - arr[i])

    return max_bi_tonic_sum



Sample Correct Code:
def max_sum(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


Asserts:
assert max_sum([1, 15, 51, 45, 33, 100, 12, 18, 9], 9) == 194
assert max_sum([80, 60, 30, 40, 20, 10], 6) == 210
assert max_sum([2, 3 ,14, 16, 21, 23, 29, 30], 8) == 138


Tests:
Test 1 of 3: PASS
Test 2 of 3: PASS
Test 3 of 3: PASS

Test 245 of 974: 176/245 (71.83673469387755%): success