You are given array A of size n. You need to find the maximum-sum sub-array with the condition that you are allowed to skip at most one element.
Example 1:
Input:
n = 5
A[] = {1,2,3,-4,5}
Output: 11
Explanation: We can get maximum sum
subarray by skipping -4.
Example 2:
Input:
n = 8
A[] = {-2,-3,4,-1,-2,1,5,-3}
Output: 9
Explanation: We can get maximum sum
subarray by skipping -2 as [4,-1,1,5]
sums to 9, which is the maximum
achievable sum.
Your Task:
Your task is to complete the function maxSumSubarray that take array and size as parameters and returns the maximum sum.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= n <= 100
-10^{3} <= A_{i}<= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: # Your task is to complete this function



class Solution:
    #Function to return maximum sum subarray by removing at most one element.
    def maxSumSubarray(self, arr, n):
        # Code here


Solutions:
class Solution:

	def maxSumSubarray(self, arr, n):
		left = [0] * n
		right = [0] * n
		right[-1] = arr[-1]
		left[0] = arr[0]
		ans = left[0]
		for i in range(1, n):
			left[i] = max(left[i - 1] + arr[i], arr[i])
			ans = max(ans, left[i])
			right[n - 1 - i] = max(right[n - i] + arr[n - 1 - i], arr[n - 1 - i])
		ans = max(ans, right[1])
		for i in range(1, n - 1):
			ans = max(ans, left[i - 1] + right[i + 1])
		ans = max(ans, left[n - 2])
		return ans


class Solution:

	def maxSumSubarray(self, arr, n):
		m = arr[0]
		for i in range(n):
			s = 0
			neg = arr[i]
			for j in range(i, n):
				if arr[j] < 0:
					if neg < 0:
						s += max(neg, arr[j])
					neg = min(neg, arr[j])
				else:
					s += arr[j]
				m = max(s, m)
		return m


class Solution:

	def maxSumSubarray(self, arr, n):
		max_ending_here = [0] * n
		max_ending_here[0] = arr[0]
		for i in range(1, n):
			max_ending_here[i] = max(arr[i], max_ending_here[i - 1] + arr[i])
		max_starting_here = [0] * n
		max_starting_here[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			max_starting_here[i] = max(arr[i], max_starting_here[i + 1] + arr[i])
		max_sum = max(max_ending_here)
		for i in range(1, n - 1):
			max_sum = max(max_sum, max_ending_here[i - 1] + max_starting_here[i + 1])
		return max_sum


import math

class Solution:

	def maxSumSubarray(self, arr, n):
		lsum = [0] * n
		rsum = [0] * n
		lsum[0] = arr[0]
		rsum[-1] = arr[-1]
		mx = lsum[0]
		for i in range(1, n):
			lsum[i] = max(arr[i], arr[i] + lsum[i - 1])
			mx = max(mx, lsum[i])
		for i in range(n - 2, -1, -1):
			rsum[i] = max(arr[i], arr[i] + rsum[i + 1])
		for j in range(1, n - 1):
			mx = max(mx, lsum[j - 1] + rsum[j + 1])
		return mx


class Solution:

	def maxSumSubarray(self, arr, n):
		cmax = arr[0]
		mmax = arr[0]
		fw = [0] * n
		fw[0] = arr[0]
		bw = [0] * n
		bw[-1] = arr[-1]
		for i in range(1, n):
			cmax = max(cmax + arr[i], arr[i])
			fw[i] = cmax
			mmax = max(mmax, cmax)
		cmax = arr[-1]
		mmax = arr[-1]
		for i in range(n - 2, -1, -1):
			cmax = max(cmax + arr[i], arr[i])
			bw[i] = cmax
			mmax = max(mmax, cmax)
		for i in range(1, n - 1):
			mmax = max(mmax, fw[i - 1] + bw[i + 1])
		mmax = max(mmax, fw[n - 2], bw[1])
		return mmax


from collections import deque
from sys import maxsize

class Solution:

	def maxSumSubarray(self, arr, n):
		lps = []
		rps = deque()
		rsum = lsum = -maxsize
		for i in range(n):
			lsum = max(arr[i] + lsum, arr[i])
			rsum = max(arr[n - i - 1] + rsum, arr[n - i - 1])
			lps.append(lsum)
			rps.appendleft(rsum)
		ans = max(rps[0], lps[n - 1])
		for i in range(1, n - 1):
			ans = max(lps[i - 1] + rps[i + 1], ans, lps[i])
		return ans


class Solution:

	def maxSumSubarray(self, arr, n):
		dpf = [0 for _ in range(n)]
		dpf[0] = arr[0]
		arrb = arr[::-1]
		msf = arr[0]
		dpb = [0 for _ in range(n)]
		dpb[0] = arrb[0]
		for i in range(1, n):
			if arr[i] + dpf[i - 1] > arr[i]:
				dpf[i] = arr[i] + dpf[i - 1]
			else:
				dpf[i] = arr[i]
			msf = max(dpf[i], msf)
		for i in range(1, n):
			if arrb[i] + dpb[i - 1] > arrb[i]:
				dpb[i] = arrb[i] + dpb[i - 1]
			else:
				dpb[i] = arrb[i]
			msf = max(dpb[i], msf)
		for i in range(1, n - 1):
			msf = max(msf, dpf[i - 1] + dpb[n - 2 - i])
		return msf


class Solution:

	def maxSumSubarray(self, arr, n):
		maxi = -float('inf')
		p = 0
		for i in range(n):
			if arr[i] > 0:
				continue
			p += 1
			c = arr.copy()
			k = i
			r = c[0]
			for j in range(1, n):
				if j == k:
					continue
				r = max(0, r + arr[j], arr[j])
				maxi = max(r, maxi)
		if maxi == -float('inf'):
			maxi = sum(arr)
		elif p == n or maxi < max(arr):
			maxi = max(arr)
		return maxi


class Solution:

	def maxSumSubarray(self, A, n):
		max_here = A[0]
		pref = [0] * n
		pref[0] = A[0]
		for i in range(1, n):
			max_here = max(A[i], max_here + A[i])
			pref[i] = max_here
		max_here = A[-1]
		suff = [0] * n
		suff[-1] = A[-1]
		max_so_far = A[-1]
		for i in range(n - 2, -1, -1):
			max_here = max(A[i], max_here + A[i])
			max_so_far = max(max_so_far, max_here)
			suff[i] = max_here
		ans = max_so_far
		for i in range(1, n - 1):
			ans = max(ans, pref[i - 1] + suff[i + 1])
		return ans


class Solution:

	def maxSumSubarray(self, arr, n):
		fk = [0] * n
		bk = [0] * n
		temp = 0
		for i in range(n):
			temp = max(temp + arr[i], arr[i])
			fk[i] = temp
		temp = 0
		ans = -10 ** 9
		for i in range(n - 1, -1, -1):
			temp = max(temp + arr[i], arr[i])
			ans = max(ans, temp)
			bk[i] = temp
		for i in range(1, n - 1):
			sm = fk[i - 1] + bk[i + 1]
			ans = max(ans, sm)
		return ans


class Solution:

	def maxSumSubarray(self, arr, n):
		fk = [0] * n
		bk = [0] * n
		temp = 0
		for i in range(n):
			temp = max(temp + arr[i], arr[i])
			fk[i] = temp
		temp = 0
		ans = -10 ** 9
		for i in range(n - 1, -1, -1):
			temp = max(temp + arr[i], arr[i])
			ans = max(ans, temp)
			bk[i] = temp
		for i in range(1, n - 1):
			a = fk[i - 1] if i > 0 else 0
			b = bk[i + 1] if i < n - 1 else 0
			sm = a + b
			ans = max(ans, sm)
		return ans


class Solution:

	def maxSumSubarray(self, arr, n):
		left = [0] * n
		left[0] = arr[0]
		for i in range(1, n):
			left[i] = max(arr[i], left[i - 1] + arr[i])
		max_sum = max(-123456789, arr[n - 1])
		right = [0] * n
		right[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			right[i] = max(arr[i], right[i + 1] + arr[i])
			max_sum = max(max_sum, right[i])
		for i in range(1, n - 1):
			curr_sum = left[i - 1] + right[i + 1]
			max_sum = max(curr_sum, max_sum)
		return max_sum


class Solution:

	def maxSumSubarray(self, arr, n):
		dpf = [0] * n
		dpr = [0] * n
		csum = arr[0]
		gsum = arr[0]
		dpf[0] = arr[0]
		for i in range(1, n):
			if csum >= 0:
				csum += arr[i]
			else:
				csum = arr[i]
			dpf[i] = csum
			gsum = max(gsum, csum)
		gsum = max(gsum, arr[n - 1])
		csum = arr[n - 1]
		dpr[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			if csum >= 0:
				csum += arr[i]
			else:
				csum = arr[i]
			dpr[i] = csum
			gsum = max(gsum, csum)
		ans = gsum
		for i in range(1, n - 1):
			ans = max(dpf[i - 1] + dpr[i + 1], ans)
		return ans


class Solution:

	def maxSumSubarray(self, arr, n):
		ans = [[max(arr[0], 0), 0]]
		t = max(0, ans[0][0], ans[0][1])
		for i in range(1, len(arr)):
			p = max(0, ans[-1][0] + arr[i], arr[i])
			q = max(0, ans[-1][1] + arr[i], ans[-1][0])
			t = max(t, p, q)
			ans.append([p, q])
		if t == 0 and t not in arr:
			return max(arr)
		return t


class Solution:

	def maxSumSubarray(self, arr, n):
		if n == 1:
			return arr[0]
		dp = [[0 for _ in range(2)] for _ in range(n)]
		dp[0][0] = arr[0]
		dp[0][1] = float('-inf')
		res = max(dp[0][0], dp[0][1])
		for i in range(1, n):
			dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i])
			dp[i][1] = max(dp[i - 1][1] + arr[i], arr[i], dp[i - 1][0])
			res = max(res, dp[i][0], dp[i][1])
		return res


class Solution:

	def maxSumSubarray(self, arr, n):
		fw = [0 for i in range(n)]
		bw = [0 for i in range(n)]
		curmax = arr[0]
		maxsofar = arr[0]
		fw[0] = curmax
		for i in range(1, n):
			curmax = max(arr[i], curmax + arr[i])
			maxsofar = max(maxsofar, curmax)
			fw[i] = curmax
		curmax = maxsofar = bw[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			curmax = max(arr[i], curmax + arr[i])
			maxsofar = max(maxsofar, curmax)
			bw[i] = curmax
		final = maxsofar
		for i in range(1, n - 1):
			final = max(final, fw[i - 1] + bw[i + 1])
		return final


class Solution:

	def maxSumSubarray(self, arr, n):
		lis = list()
		Sum = -2 ** 63
		boo = False
		cnt = 0
		for i in arr:
			if i < 0:
				cnt += 1
		if cnt == n:
			return max(arr)
		for i in range(n + 1):
			s = list()
			for j in range(i, n):
				s.append(arr[j])
				cur_sum = sum(s)
				Min = 2 ** 63
				for ele in s:
					if ele < 0:
						Min = min(Min, ele)
				if Min < 0:
					cur_sum += abs(Min)
				Sum = max(Sum, cur_sum)
		return Sum


class Solution:

	def maxSumSubarray(self, arr, n):
		fw = [None] * n
		bw = [None] * n
		if n == 1:
			return arr[0]
		bw[0] = arr[0]
		for i in range(1, n):
			bw[i] = max(arr[i], arr[i] + bw[i - 1])
		fw[n - 1] = arr[n - 1]
		for i in reversed(range(n - 1)):
			fw[i] = max(arr[i], arr[i] + fw[i + 1])
		fans = max(bw)
		for i in range(1, n - 1):
			fans = max(fans, fw[i + 1] + bw[i - 1])
		return fans


class Solution:

	def maxSumSubarray(self, arr, n):
		fw = [0 for i in range(n)]
		bw = [0 for i in range(n)]
		su = sum(arr)
		curr_sum = arr[0]
		fw[0] = arr[0]
		for i in range(1, n):
			curr_sum = max(arr[i], curr_sum + arr[i])
			fw[i] = curr_sum
		curr_sum = arr[n - 1]
		best_sum = arr[n - 1]
		bw[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			curr_sum = max(arr[i], curr_sum + arr[i])
			best_sum = max(best_sum, curr_sum)
			bw[i] = curr_sum
		sol = [0 for i in range(n)]
		s = best_sum
		for i in range(1, n - 1):
			s = max(s, fw[i - 1] + bw[i + 1])
		return s


class Solution:

	def maxSumSubarray(self, arr, n):
		if n == 1:
			return max(0, arr[0])
		inf = -float('inf')
		l = [[inf, inf]] * n
		csum = arr[0]
		l[1] = [csum, csum]
		ma = csum
		for i in range(2, n):
			csum = max(csum + arr[i - 1], arr[i - 1])
			ma = max(csum, ma)
			l[i] = [csum, ma]
		r = [[inf, inf]] * n
		csum = arr[-1]
		r[-2] = [csum, csum]
		ma = csum
		for i in range(n - 3, -1, -1):
			csum = max(csum + arr[i + 1], arr[i + 1])
			ma = max(csum, ma)
			r[i] = [csum, ma]
		m = -float('inf')
		for i in range(n):
			m = max(m, l[i][0] + r[i][0], l[i][1], r[i][1])
		csum = arr[0]
		ma = csum
		for i in range(1, n):
			csum = max(csum + arr[i], arr[i])
			ma = max(ma, csum)
		return max(m, ma)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		print(Solution().maxSumSubarray(arr, n))


class Solution:

	def maxSumSubarray(self, arr, n):
		fw = [0 for k in range(n)]
		bw = [0 for k in range(n)]
		(cur_max, max_so_far) = (arr[0], arr[0])
		fw[0] = cur_max
		for i in range(1, n):
			cur_max = max(arr[i], cur_max + arr[i])
			max_so_far = max(max_so_far, cur_max)
			fw[i] = cur_max
		cur_max = max_so_far = bw[n - 1] = arr[n - 1]
		i = n - 2
		while i >= 0:
			cur_max = max(arr[i], cur_max + arr[i])
			max_so_far = max(max_so_far, cur_max)
			bw[i] = cur_max
			i -= 1
		fans = max_so_far
		for i in range(1, n - 1):
			fans = max(fans, fw[i - 1] + bw[i + 1])
		return fans


class Solution:

	def maxSumSubarray(self, arr, n):
		sm = nm = gm = -10000
		for i in arr:
			sm = max(sm + i, nm)
			nm = max(nm + i, i)
			gm = max(gm, sm, nm)
		return gm


class Solution:

	def maxSumSubarray(self, arr, n):
		lsum = [0] * n
		rsum = [0] * n
		maxSum = arr[0]
		maxSubArraySum = arr[0]
		lsum[0] = arr[0]
		for i in range(1, n):
			maxSubArraySum = max(maxSubArraySum + arr[i], arr[i])
			lsum[i] = maxSubArraySum
			maxSum = max(maxSum, lsum[i])
		rsum[n - 1] = arr[n - 1]
		maxSubArraySum = arr[n - 1]
		for j in range(n - 2, -1, -1):
			maxSubArraySum = max(maxSubArraySum + arr[j], arr[j])
			rsum[j] = maxSubArraySum
		maxVal = float('-inf')
		for i in range(n):
			fw = 0
			bw = 0
			if i - 1 >= 0:
				fw = lsum[i - 1]
			if i + 1 < n:
				bw = rsum[i + 1]
			maxVal = max(fw + bw, maxVal)
		return max(maxVal, maxSum)


class Solution:

	def maxSumSubarray(self, arr, n):
		prenotd = arr[0]
		predel = 0
		maxn = arr[0]
		for i in range(1, n):
			predel = max(prenotd, predel + arr[i])
			prenotd = max(arr[i], prenotd + arr[i])
			cur = max(prenotd, predel)
			maxn = max(cur, maxn)
		return maxn


class Solution:

	def maxSumSubarray(self, arr, n):
		Maxsum = -1001
		cond = 0
		for i in arr:
			if i < 0:
				cond += 1
		if cond == n:
			return max(arr)
		for i in range(0, n):
			for j in range(0, n - i):
				Maxsum = max(Maxsum, sum(arr[j:j + i + 1]) - min(arr[j:j + i + 1]), sum(arr[j:j + i + 1]))
		return Maxsum