Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.
Note that the subarray needs to be non-empty after deleting one element.
 
Example 1:
Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.
Example 2:
Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:
Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

 
Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        

Solutions:
import sys

class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		ignore = 0
		not_ignore = 0
		res = -sys.maxsize
		for i in arr:
			if i >= 0:
				ignore += i
				not_ignore += i
			else:
				if ignore == 0:
					ignore += i
				else:
					ignore = max(ignore + i, not_ignore)
				not_ignore += i
			res = max(res, ignore)
			if ignore < 0:
				ignore = 0
			if not_ignore < 0:
				not_ignore = 0
		return res


class Solution(object):

	def maximumSum(self, arr):
		(dp, res) = ([arr[0], 0], arr[0])
		for i in range(1, len(arr)):
			dp[1] = max(dp[0], dp[1] + arr[i])
			dp[0] = max(arr[i], arr[i] + dp[0])
			res = max(res, dp[0], dp[1])
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		max_ending_here0 = n * [arr[0]]
		max_ending_here1 = n * [arr[0]]
		for i in range(1, n):
			max_ending_here0[i] = max(max_ending_here0[i - 1] + arr[i], arr[i])
			max_ending_here1[i] = max(max_ending_here1[i - 1] + arr[i], arr[i])
			if i >= 2:
				max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i - 2] + arr[i])
		return max(max_ending_here1)


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if not arr:
			return None
		max_sum = [0] * len(arr)
		max_sum_one_del = [0] * len(arr)
		max_sum[0] = arr[0]
		max_sum_one_del[0] = arr[0]
		for i in range(1, len(arr)):
			max_sum[i] = max(max_sum[i - 1] + arr[i], arr[i])
			max_sum_one_del[i] = max(max_sum_one_del[i - 1] + arr[i], arr[i])
			if i > 1:
				max_sum_one_del[i] = max(max_sum[i - 2] + arr[i], max_sum_one_del[i])
		return max(max_sum_one_del)


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		M = max(arr)
		if M < 0:
			return M
		kad = arr[:]
		curr = 0
		for i in range(len(arr)):
			kad[i] = max(0, curr + kad[i])
			curr = kad[i]
		curr = 0
		revkad = arr[:]
		for i in range(len(arr) - 1, -1, -1):
			revkad[i] = max(0, curr + revkad[i])
			curr = revkad[i]
		ans = max(kad)
		for i in range(1, len(arr) - 1):
			ans = max(ans, kad[i - 1] + revkad[i + 1])
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		neg = []
		for i in range(len(arr)):
			if arr[i] < 0:
				neg.append(i)
		if len(neg) == 0:
			return sum(arr)
		if len(neg) == len(arr):
			return max(arr)
		x1 = [0] * len(neg)
		x2 = [0] * len(neg)
		x1[0] = sum(arr[:neg[0]])
		x2[-1] = sum(arr[neg[-1] + 1:])
		for j in range(1, len(neg)):
			for k in range(neg[j - 1] + 1, neg[j]):
				x1[j] += arr[k]
			if x1[j - 1] + arr[neg[j - 1]] > 0:
				x1[j] += x1[j - 1] + arr[neg[j - 1]]
		for j in range(len(neg) - 2, -1, -1):
			for k in range(neg[j] + 1, neg[j + 1]):
				x2[j] += arr[k]
			if x2[j + 1] + arr[neg[j + 1]] > 0:
				x2[j] += x2[j + 1] + arr[neg[j + 1]]
		m = arr[0]
		for i in range(len(x1)):
			m = max(m, x1[i] + x2[i])
		return m


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		bestFromS = [arr[0]]
		for i in range(1, len(arr)):
			bestFromS.append(max(arr[i], arr[i] + bestFromS[i - 1]))
		bestFromE = [0] * len(arr)
		bestFromE[len(arr) - 1] = arr[len(arr) - 1]
		for i in range(len(arr) - 2, -1, -1):
			bestFromE[i] = max(bestFromE[i + 1] + arr[i], arr[i])
		res = max(bestFromS)
		for i in range(len(arr)):
			before = 0 if i == 0 else bestFromS[i - 1]
			after = 0 if i == len(arr) - 1 else bestFromE[i + 1]
			res = max(res, before + after)
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		max1: int = arr[0]
		max0: int = arr[0]
		res: int = arr[0]
		for a in arr[1:]:
			max1 = max(max1 + a, max0, a)
			max0 = max(max0 + a, a)
			res = max(res, max1)
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if not arr:
			return 0
		if len(arr) == 1:
			return arr[0]
		fw = [arr[0]]
		bw = [arr[-1]]
		cur_max = max_so_far = arr[0]
		for num in arr[1:]:
			cur_max = max(cur_max + num, num)
			max_so_far = max(max_so_far, cur_max)
			fw.append(cur_max)
		cur_max = arr[-1]
		for num in arr[:-1][::-1]:
			cur_max = max(cur_max + num, num)
			max_so_far = max(max_so_far, cur_max)
			bw.append(cur_max)
		bw = bw[::-1]
		for i in range(1, len(arr) - 1):
			max_so_far = max(max_so_far, fw[i - 1] + bw[i + 1])
		return max_so_far


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		ans = -math.inf
		left = [-1] * n
		right = [-1] * n
		for i in range(n):
			left[i] = max(arr[i], left[i - 1] + arr[i]) if i > 0 else arr[i]
			ans = max(ans, left[i])
		for i in range(n - 1, -1, -1):
			right[i] = max(arr[i], right[i + 1] + arr[i]) if i < n - 1 else arr[i]
			ans = max(ans, right[i])
		for i in range(1, n - 1):
			ans = max(ans, left[i - 1] + right[i + 1])
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		dps = [elem for elem in arr]
		dpe = [elem for elem in arr]
		dpt = [elem for elem in arr]
		for i in range(len(arr)):
			if i != 0:
				dpe[i] = max(dpe[i], dpe[i] + dpe[i - 1])
				ip = len(arr) - i - 1
				dps[ip] = max(dps[ip], dps[ip] + dps[ip + 1])
		for i in range(len(arr)):
			if i != 0 and i != len(arr) - 1:
				dpt[i] = dpe[i - 1] + dps[i + 1]
			elif i == 0:
				dpt[i] = dps[i + 1]
			else:
				dpt[i] = dpe[i - 1]
		return max(max(dpt), max(dpe), max(dps))


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		s = sum(arr)
		pref = [0]
		for arr_i in arr:
			pref.append(pref[-1] + arr_i)
		for i in range(1, n + 1):
			pref[i] = min(pref[i], pref[i - 1])
		suf = [0]
		for arr_i in arr[::-1]:
			suf.append(suf[-1] + arr_i)
		for i in range(1, n + 1):
			suf[i] = min(suf[i], suf[i - 1])
		ans = s
		for i in range(n):
			if arr[i] < 0:
				if i - 1 >= 0:
					ans = max(ans, s - arr[i] - pref[i - 1] - suf[n - 1 - i])
				if n - 2 - i >= 0:
					ans = max(ans, s - arr[i] - pref[i] - suf[n - 2 - i])
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		(ans, dp1, dp2, lr, rl) = (-math.inf, [None] * len(arr), [None] * len(arr), 0, 0)
		for (i, val) in enumerate(arr):
			(lr, rl) = (max(lr, 0) + val, max(rl, 0) + arr[len(arr) - 1 - i])
			(dp1[i], dp2[len(arr) - 1 - i]) = (lr, rl)
			ans = max(ans, lr, rl)
		for i in range(1, len(arr) - 1):
			if arr[i] < 0:
				ans = max(ans, dp1[i - 1] + dp2[i + 1])
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		A = arr
		N = len(A)
		dp0 = [None] * N
		dp1 = [None] * N
		cur = A[0]
		dp0[0] = cur
		for i in range(1, N):
			cur = max(cur + A[i], A[i])
			dp0[i] = cur
		cur = A[-1]
		dp1[-1] = cur
		for i in range(N - 2, -1, -1):
			cur = max(cur + A[i], A[i])
			dp1[i] = cur
		ans = max(dp0)
		for (i, x) in enumerate(A):
			if i + 2 < N:
				ans = max(ans, dp0[i] + dp1[i + 2])
		return ans


class Solution:

	def maximumSum(self, nums: List[int]) -> int:
		n = len(nums)
		dp0 = [0 for i in range(n)]
		dp1 = [0 for i in range(n)]
		dp0[0] = nums[0]
		dp1[0] = nums[0]
		ans = nums[0]
		for i in range(1, n):
			dp0[i] = max(dp0[i - 1] + nums[i], nums[i])
			dp1[i] = max(dp1[i - 1] + nums[i], nums[i])
			if i > 1:
				dp1[i] = max(nums[i], dp1[i - 1] + nums[i], nums[i] + dp0[i - 2])
			ans = max(ans, dp0[i], dp1[i])
		return ans


import math

class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		dp = []
		for i in range(n):
			dp.append([arr[i], arr[i]])
		for i in range(1, n):
			dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])
			if i > 1:
				dp[i][1] = max(arr[i], dp[i - 1][1] + arr[i], dp[i - 2][0] + arr[i])
		ans = -math.inf
		for i in range(n):
			ans = max(ans, max(dp[i][0], dp[i][1]))
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[0 for _ in range(2)] for _ in range(n)]
		dp[0] = [arr[0]] * 2
		for i in range(1, n):
			dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])
			dp[i][1] = max(dp[i][0], dp[i - 1][0], dp[i - 1][1] + arr[i])
		return max(map(lambda l: max(l), dp))


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		res = float('-inf')
		max_ending_here0 = 3 * [arr[0]]
		max_ending_here1 = 3 * [arr[0]]
		for i in range(1, len(arr)):
			max_ending_here0[i % 3] = max(max_ending_here0[(i - 1) % 3] + arr[i], arr[i])
			max_ending_here1[i % 3] = max(max_ending_here1[(i - 1) % 3] + arr[i], arr[i])
			if i >= 2:
				max_ending_here1[i % 3] = max(max_ending_here1[i % 3], max_ending_here0[(i - 2) % 3] + arr[i])
			res = max(res, max_ending_here1[i % 3])
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		nodel = [arr[0]]
		for i in range(1, len(arr)):
			nodel.append(arr[i] + max(0, nodel[i - 1]))
		onedel = [arr[0]]
		for i in range(1, len(arr)):
			onedel.append(max(nodel[i], nodel[i - 1], arr[i] + onedel[-1]))
		return max(onedel)


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		(mx, n) = (float('-inf'), len(arr))
		(left, right) = ([float('-inf') for _ in range(len(arr))], [float('-inf') for _ in range(len(arr))])
		for i in range(len(arr)):
			left[i] = max(arr[i], arr[i] + left[i - 1]) if i > 0 else arr[0]
			right[n - i - 1] = max(arr[n - i - 1], arr[n - i - 1] + right[n - i]) if i > 0 else arr[-1]
		for i in range(len(arr)):
			mx = max(mx, arr[i])
			if 2 * arr[i] != left[i] + right[i]:
				mx = max(mx, left[i] + right[i] - 2 * arr[i])
		return mx


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		dp = [[0] * 2 for i in range(len(arr))]
		dp[0][0] = arr[0]
		for i in range(1, len(arr)):
			dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])
			dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0])
		ans = float('-inf')
		for i in range(len(arr)):
			ans = max(ans, dp[i][0], dp[i][1])
		if ans == 0:
			return max(arr)
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		max_res = [0] * len(arr)
		max_start = [0] * len(arr)
		max_end = [0] * len(arr)
		for (i, n) in enumerate(arr):
			max_end[i] = n if i == 0 else max(n, max_end[i - 1] + n)
		print(max_end)
		for (i, n) in list(enumerate(arr))[::-1]:
			max_start[i] = n if i == len(arr) - 1 else max(n, max_start[i + 1] + n)
		print(max_start)
		for (i, n) in enumerate(arr):
			max_left = n if i == 0 else max_end[i - 1]
			max_right = n if i == len(arr) - 1 else max_start[i + 1]
			max_res[i] = max(max_left, max_right, max_left + max_right)
		print(max_res)
		return max(max_res)


class Solution:

	def maximumSum(self, a: List[int]) -> int:
		max_so_far = -sys.maxsize
		max_ending_here = 0
		size = len(a)
		dp = [-sys.maxsize] * size
		dp[0] = a[0]
		dp1 = [-sys.maxsize] * size
		dp1[0] = a[0]
		for i in range(1, size):
			dp[i] = max(a[i], dp[i - 1] + a[i])
			dp1[i] = max(a[i], dp1[i - 1] + a[i])
			if i >= 2:
				dp1[i] = max(dp1[i], dp[i - 2] + a[i])
		return max(dp1)


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		dp = [[0 for _ in range(2)] for _ in range(len(arr))]
		dp[0][0] = arr[0]
		dp[0][1] = arr[0]
		ans = max(dp[0])
		for i in range(1, len(arr)):
			dp[i][0] = max(dp[i - 1][0] + arr[i], dp[i - 1][1])
			dp[i][1] = max(dp[i - 1][1] + arr[i], arr[i])
			ans = max(ans, dp[i][0], dp[i][1])
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		dp = [[float('-inf')] * 2 for _ in range(n)]
		dp[0][0] = arr[0]
		dp[0][1] = float('-inf')
		for i in range(1, n):
			dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])
			dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0])
		ans = float('-inf')
		for i in range(n):
			for j in range(2):
				ans = max(ans, dp[i][j])
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		ans = arr[0]
		n = len(arr)
		s = []
		for i in range(n):
			s.append([None, None])
		s[0][0] = s[0][1] = arr[0]
		for i in range(1, n):
			s[i][0] = max(s[i - 1][0], 0) + arr[i]
			s[i][1] = max(max(s[i - 1][1], 0) + arr[i], s[i - 1][0])
			ans = max(s[i][0], s[i][1], ans)
		print(s)
		return ans


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		r = max(arr)
		if r < 0:
			return r
		l = len(arr)
		f = [0] * l
		b = [0] * l
		cur = 0
		for i in range(l):
			f[i] = cur
			cur += arr[i]
			cur = max(cur, 0)
		cur = 0
		for i in range(l - 1, -1, -1):
			b[i] = cur
			cur += arr[i]
			cur = max(cur, 0)
		return max((f[i] + b[i] for i in range(l)))


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		max_overall = arr[0]
		max_sum = arr[0]
		max_excluded = float('-inf')
		for i in range(1, len(arr)):
			max_excluded = max(max_excluded + arr[i], max_sum)
			max_sum = max(max_sum + arr[i], arr[i])
			max_overall = max(max_overall, max_sum, max_excluded)
		return max_overall


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		curr_max = [-math.inf, -math.inf]
		max_sum = -math.inf
		for num in arr:
			(curr_max[0], curr_max[1]) = (max(num, curr_max[0] + num), max(curr_max[1] + num, curr_max[0]))
			max_sum = max([max_sum, curr_max[0], curr_max[1]])
		return max_sum


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		positive = [0 for _ in range(len(arr))]
		negative = positive.copy()
		positive[0] = arr[0]
		for (i, num) in enumerate(arr[1:]):
			positive[i + 1] = max(num, positive[i] + num)
			negative[i + 1] = max(negative[i] + num, positive[i])
		return max(positive + negative[1:])


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]

		@lru_cache(None)
		def max_sum_start_at(i):
			if i == len(arr) - 1:
				return arr[-1]
			return max(arr[i], arr[i] + max_sum_start_at(i + 1))

		@lru_cache(None)
		def max_sum_end_at(j):
			if j == 0:
				return arr[0]
			return max(arr[j], arr[j] + max_sum_end_at(j - 1))
		return max(max([max_sum_start_at(i) for i in range(len(arr))]), max([max_sum_end_at(i - 1) + max_sum_start_at(i + 1) for i in range(1, len(arr) - 1)]))


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if max(arr) < 0:
			return max(arr)

		@lru_cache(maxsize=None)
		def recurse(idx, isSkipped):
			if idx == len(arr):
				return 0
			if isSkipped:
				return max(arr[idx] + recurse(idx + 1, True), 0)
			else:
				return max(arr[idx] + recurse(idx + 1, False), recurse(idx + 1, True), arr[idx])
		curMax = float('-inf')
		for i in range(len(arr)):
			curMax = max(recurse(i, False), curMax)
		return curMax


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		(max0, max1, result) = (arr[0], arr[0], arr[0])
		for n in arr[1:]:
			max1 = max(max1 + n, max0, n)
			max0 = max(max0 + n, n)
			result = max(result, max1)
		return result


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		dp = [[0] * 2 for i in range(len(arr))]
		if len(arr) == 0:
			return 0
		dp[0][0] = arr[0]
		dp[0][0] = arr[0]
		maxm = arr[0]
		for i in range(1, len(arr)):
			dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i])
			dp[i][1] = max(arr[i], dp[i - 1][1] + arr[i], dp[i - 1][0])
			maxm = max(maxm, dp[i][0], dp[i][1])
		return maxm


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		dp = [[0 for _ in range(2)] for _ in range(len(arr))]
		mins = [0 for _ in range(len(arr))]
		dp[0][0] = arr[0]
		dp[0][1] = arr[0]
		mins[0] = arr[0]
		ans = max(dp[0])
		for i in range(1, len(arr)):
			if arr[i] >= 0:
				if dp[i - 1][0] < 0:
					dp[i][0] = arr[i]
					dp[i][1] = arr[i]
					mins[i] = arr[i]
				else:
					dp[i][0] = dp[i - 1][0] + arr[i]
					dp[i][1] = max(dp[i - 1][1] + arr[i], arr[i])
					mins[i] = min(mins[i - 1], arr[i])
			elif dp[i - 1][0] < 0:
				dp[i][0] = arr[i]
				dp[i][1] = arr[i]
				mins[i] = arr[i]
			else:
				mins[i] = min(mins[i - 1], arr[i])
				dp[i][0] = max(dp[i - 1][0] + arr[i], dp[i - 1][1])
				dp[i][1] = max(dp[i - 1][1] + arr[i], arr[i])
			ans = max(ans, dp[i][0], dp[i][1])
		return ans


class Solution:

	def maximumSum(self, nums: List[int]) -> int:
		maxi = nums[0]
		sumi = nums[0]
		left = [nums[0]]
		right = [nums[-1]]
		for i in nums[1:]:
			sumi = max(i, sumi + i)
			left.append(sumi)
		t = nums[::-1]
		sumi = t[0]
		for i in t[1:]:
			sumi = max(i, sumi + i)
			right.append(sumi)
		right = right[::-1]
		l = len(nums)
		res = 0
		for i in range(l):
			res = max(res, left[i] + right[i] - 2 * nums[i])
		if res != 0:
			return res
		return max(nums)


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		if n == 1:
			return arr[0]
		maxsum = [0]
		for i in reversed(range(1, n)):
			if maxsum[-1] > 0:
				maxsum.append(maxsum[-1] + arr[i])
			else:
				maxsum.append(arr[i])
		s = 0
		result = -10 ** 6
		for (i, a) in enumerate(arr):
			r = maxsum.pop()
			if 0 < i < n - 1:
				result = max(result, s + r)
			if s > 0:
				s += a
			else:
				s = a
			result = max(result, s)
		return result


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if not arr:
			return 0
		max_del = arr[0]
		max_no_del = arr[0]
		res = arr[0]
		for i in range(1, len(arr)):
			max_del = max(max_del + arr[i], max_no_del, arr[i])
			max_no_del = max(max_no_del + arr[i], arr[i])
			res = max(res, max_del)
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		(nodel, delected) = (0, 0)
		res = float('-inf')
		for num in arr:
			delected = max(nodel, delected + num)
			nodel = max(nodel, 0) + num
			res = max(nodel, delected, res)
		return res

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]
		(nodel, delected) = (arr[0], 0)
		res = arr[0]
		for num in arr[1:]:
			delected = max(nodel, delected + num)
			nodel = max(nodel, 0) + num
			res = max(nodel, delected, res)
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		n = len(arr)
		(dp0, dp1, res) = (arr[0], 0, arr[0])
		for i in range(1, n):
			(dp0, dp1) = (max(dp0 + arr[i], arr[i]), max(dp0, dp1 + arr[i]))
			res = max(dp0, dp1, res)
		return res


class Solution:

	def maximumSum(self, arr: List[int]) -> int:
		if len(arr) == 1:
			return arr[0]

		def helper(arr):
			n = len(arr)
			dp = [0] * n
			if arr == []:
				return 0
			else:
				res = 0
				curr = arr[0]
				dp[0] = arr[0]
				for i in range(1, len(arr)):
					curr = max(curr + arr[i], arr[i])
					res = max(res, curr)
					dp[i] = curr
				return (dp, res)
		(lp, best) = helper(arr)
		(rp, best) = helper(arr[::-1])
		rp = rp[::-1]
		print(lp, rp)
		ans = -1
		for k in range(0, len(arr)):
			val = rp[k + 1] if k < len(arr) - 1 else 0
			val2 = lp[k - 1] if k > 0 else 0
			print(val2, val)
			ans = max(ans, best, val + val2, val, val2)
		if ans == 0:
			return -1
		return ans


class Solution:

	def maximumSum(self, a: List[int]) -> int:
		n = len(a)
		ans = skipped = not_skipped = a[-1]
		for i in range(n - 2, -1, -1):
			(not_skipped, skipped) = (max(a[i], a[i] + not_skipped, skipped), max(a[i], a[i] + skipped))
			ans = max(ans, skipped, not_skipped)
		return ans