Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.
Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)
Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
 

Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3


Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10


Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4


Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

 
Note: 

-30000 <= A[i] <= 30000
1 <= A.length <= 30000

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Divide and conquer
Skill types: Dynamic programming

Data structures

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

Solutions:
class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		if N == 0:
			return 0
		curr_max = A[0]
		global_max = A[0]
		curr_min = A[0]
		global_min = A[0]
		flag = 0
		if A[0] >= 0:
			flag = 1
		for i in range(1, N):
			if A[i] >= 0:
				flag = 1
			if curr_max >= 0:
				curr_max = curr_max + A[i]
			else:
				curr_max = A[i]
			if curr_min >= 0:
				curr_min = A[i]
			else:
				curr_min = curr_min + A[i]
			if curr_max > global_max:
				global_max = curr_max
			if curr_min < global_min:
				global_min = curr_min
		if flag == 0:
			return max(A)
		return max(global_max, sum(A) - global_min)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		curr_max = A[0]
		max_sum = A[0]
		curr_min = A[0]
		min_sum = A[0]
		for i in range(1, len(A)):
			curr_max = max(A[i], A[i] + curr_max)
			max_sum = max(curr_max, max_sum)
			curr_min = min(A[i], A[i] + curr_min)
			min_sum = min(curr_min, min_sum)
		if max_sum > 0:
			return max(sum(A) - min_sum, max_sum)
		else:
			return max(A)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if not A:
			return 0
		max_A = max(A)
		if max_A <= 0:
			return max_A
		max_sum = 0
		cur_sum = 0
		for i in range(len(A)):
			cur_sum = max(cur_sum, 0) + A[i]
			max_sum = max(max_sum, cur_sum)
		if len(A) <= 2:
			return max_sum
		right_sum = A[-1]
		right_max = [A[-1]]
		for i in A[len(A) - 2::-1]:
			right_sum += i
			right_max.append(max(right_max[-1], right_sum))
		right_max = right_max[::-1]
		left_max = A[0]
		left_sum = A[0]
		for i in range(1, len(A) - 1):
			left_sum += A[i]
			left_max = max(left_max, left_sum)
			max_sum = max(max_sum, left_max + right_max[i + 1])
		return max_sum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		mini = maxi = A[0]
		curMin = curMax = total = 0
		for num in A:
			curMin = min(curMin + num, num)
			curMax = max(curMax + num, num)
			maxi = max(maxi, curMax)
			mini = min(mini, curMin)
			total += num
		return max(maxi, total - mini) if maxi > 0 else maxi


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def _get_max(lo, hi, flag):
			m = float('-inf')
			s = 0
			for i in range(lo, hi):
				s = max(s, 0) + flag * A[i]
				m = max(m, s)
			return m
		s = sum(A)
		return max(_get_max(0, len(A), 1), s + _get_max(0, len(A) - 1, -1), s + _get_max(1, len(A), -1))


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		mx = curr = A[0]
		cumSum = [A[0]]
		for i in range(1, len(A)):
			if curr >= 0:
				curr += A[i]
			else:
				curr = A[i]
			mx = max(mx, curr)
			cumSum.append(cumSum[-1] + A[i])
		revCumSum = []
		curr = 0
		for x in reversed(A):
			curr += x
			if revCumSum:
				revCumSum.append(max(revCumSum[-1], curr))
			else:
				revCumSum.append(curr)
		for i in range(len(A) - 1):
			mx = max(mx, cumSum[i] + revCumSum[len(A) - 2 - i])
		mx = max(mx, cumSum[-1])
		return mx


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def maxSubarray(A):
			dp = [0] * len(A)
			max_c = A[0]
			flag = True
			for (idx, num) in enumerate(A):
				if num < 0:
					flag = False
				if idx == 0:
					dp[0] = num
				else:
					dp[idx] = max(num, dp[idx - 1] + num)
			return (max(dp), flag)
		(temp, nonNeg) = maxSubarray(A)
		if nonNeg:
			return temp
		res = float('-inf')
		rightWindow = [A[0]] + [0] * (len(A) - 1)
		for (idx, i) in enumerate(A[1:]):
			rightWindow[idx + 1] = i + rightWindow[idx]
		currMax = float('-inf')
		MaxIdx = float('inf')
		reversedA = A.reverse()
		leftWindow = [A[0]] + [0] * (len(A) - 1)
		for (idx, i) in enumerate(A[1:]):
			leftWindow[idx + 1] = i + leftWindow[idx]
			if MaxIdx >= len(A) - idx - 1:
				currMax = max(rightWindow[:len(A) - idx - 1])
				MaxIdx = rightWindow.index(currMax)
			res = max(res, currMax + leftWindow[idx])
		return max(res, temp)


import heapq

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		best = A[0]
		heap = [(0, 0)]
		cumsums = [0]
		for n in A:
			cumsums.append(cumsums[-1] + n)
		for n in A:
			cumsums.append(cumsums[-1] + n)
		for i in range(1, len(cumsums)):
			while len(heap) > 0 and i - heap[0][1] > N:
				heapq.heappop(heap)
			best = max(best, cumsums[i] - heap[0][0])
			heapq.heappush(heap, (cumsums[i], i))
		return best


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		(total, maxSum, curMax, minSum, curMin) = (0, A[0], 0, A[0], 0)
		for a in A:
			curMax = max(curMax + a, a)
			maxSum = max(maxSum, curMax)
			curMin = min(curMin + a, a)
			minSum = min(minSum, curMin)
			total += a
		return max(maxSum, total - minSum) if maxSum > 0 else maxSum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		totalSum = sum(A)
		curr = A[0]
		maxSum = A[0]
		for i in range(1, len(A)):
			if A[i] + curr > A[i]:
				curr = A[i] + curr
			else:
				curr = A[i]
			maxSum = max(maxSum, curr)
		curr = A[0]
		minSum = totalSum
		for i in range(1, len(A)):
			curr = min(A[i] + curr, A[i])
			minSum = min(minSum, curr)
		if totalSum == minSum:
			return maxSum
		return max(totalSum - minSum, maxSum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kadane(array):
			global_max = array[0]
			local_max = array[0]
			for i in range(1, len(array)):
				if local_max < 0:
					local_max = 0
				local_max = array[i] + local_max
				if local_max > global_max:
					global_max = local_max
			return global_max

		def kadane_inverse(array):
			global_min = array[0]
			local_min = array[0]
			for i in range(1, len(array)):
				if local_min > 0:
					local_min = 0
				local_min = array[i] + local_min
				if local_min < global_min:
					global_min = local_min
			return global_min
		total = sum(A)
		inv = kadane_inverse(A)
		reg = kadane(A)
		if total == inv:
			return reg
		return max(total - inv, reg)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def maxSubarray(A):
			dp = [0] * len(A)
			max_c = A[0]
			for (idx, num) in enumerate(A):
				if idx != 0:
					dp[idx] = max(num, dp[idx - 1] + num)
				else:
					dp[0] = num
			return max(dp)
		temp = maxSubarray(A)
		res = float('-inf')
		rightMax = [max(A[0], 0)] + [0] * (len(A) - 1)
		currMax = max(A[0], 0)
		rightWindow = [A[0]] + [0] * (len(A) - 1)
		for (idx, i) in enumerate(A[1:]):
			currMax = max(i + rightWindow[idx], currMax)
			rightMax[idx + 1] = currMax
			rightWindow[idx + 1] = i + rightWindow[idx]
		reversedA = A.reverse()
		leftWindow = [A[0]] + [0] * (len(A) - 1)
		for (idx, i) in enumerate(A[1:]):
			leftWindow[idx + 1] = i + leftWindow[idx]
			currMax = rightMax[len(A) - idx - 2]
			res = max(res, currMax + leftWindow[idx])
		return max(res, temp)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		cur_sum = A[0]
		result1 = A[0]
		for i in range(1, n):
			cur_sum = max(A[i], cur_sum + A[i])
			result1 = max(cur_sum, result1)
		if n == 1:
			return result1
		cur_sum = A[1]
		result2 = A[1]
		for i in range(2, n - 1):
			cur_sum = min(A[i], cur_sum + A[i])
			result2 = min(cur_sum, result2)
		return max(result1, sum(A) - result2)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		if n == 1:
			return A[0]

		def kadane(it):
			max_ = current = float('-inf')
			for num in it:
				current = num + max(current, 0)
				max_ = max(max_, current)
			return max_
		total = sum(A)
		max1 = kadane((num for num in A))
		max2 = total + kadane((-A[idx] for idx in range(n - 1)))
		max3 = total + kadane((-A[idx] for idx in range(1, n)))
		return max(max1, max2, max3)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if A is None or not A:
			return 0
		N = len(A)
		A = A + A
		acc = [0]
		for d in A:
			acc.append(acc[-1] + d)
		ret = -sys.maxsize
		queue = deque([0])
		for j in range(1, 2 * N):
			while queue and queue[0] < j - N:
				queue.popleft()
			ret = max(ret, acc[j] - acc[queue[0]])
			while queue and acc[queue[-1]] >= acc[j]:
				queue.pop()
			queue.append(j)
		return ret


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		sm = sum(A)
		mx = mn = cur_mx = cur_mn = A[0]
		for i in range(1, len(A)):
			cur_mn = min(cur_mn + A[i], A[i])
			mn = min(mn, cur_mn)
			cur_mx = max(cur_mx + A[i], A[i])
			mx = max(mx, cur_mx)
		return max(mx, mn if mn == sm else sm - mn)


class Solution:

	def maxSubarraySumCircular(self, a: List[int]) -> int:
		n = len(a)
		ans = float('-inf')
		current = 0
		for num in a:
			current = num + max(0, current)
			ans = max(ans, current)
		right_sum = [0] * n
		right_sum[-1] = a[-1]
		right_most = [float('-inf')] * n
		right_most[-1] = right_sum[-1]
		for i in range(n - 2, -1, -1):
			right_sum[i] = right_sum[i + 1] + a[i]
			right_most[i] = max(right_sum[i], right_most[i + 1])
		left_sum = 0
		for i in range(n - 2):
			left_sum += a[i]
			ans = max(ans, left_sum + right_most[i + 2])
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		max_subarray = float('-inf')
		cur_max_subarray = 0
		min_subarray = float('inf')
		cur_min_subarray = 0
		total = 0
		max_value = float('-inf')
		for num in A:
			cur_max_subarray += num
			if cur_max_subarray < 0:
				cur_max_subarray = 0
			else:
				max_subarray = max(max_subarray, cur_max_subarray)
			cur_min_subarray += num
			if cur_min_subarray > 0:
				cur_min_subarray = 0
			else:
				min_subarray = min(min_subarray, cur_min_subarray)
			total += num
			max_value = max(max_value, num)
		if max_value <= 0:
			return max_value
		return max(max_subarray, total - min_subarray)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		dp = [0]
		for _ in range(2):
			for num in A:
				dp.append(dp[-1] + num)
		res = A[0]
		deque = collections.deque([0])
		for j in range(1, len(dp)):
			if deque[0] < j - len(A):
				deque.popleft()
			res = max(res, dp[j] - dp[deque[0]])
			while deque and dp[j] <= dp[deque[-1]]:
				deque.pop()
			deque.append(j)
		return res
		cur_max = -float('inf')
		dp = [0]
		for num in A:
			dp.append(dp[-1] + num)
		for i in range(len(A)):
			for j in range(i + 1, i + len(A) + 1):
				if j <= len(A):
					cur_max = max(cur_max, dp[j] - dp[i])
				else:
					cur_max = max(cur_max, dp[len(A)] - dp[i] + dp[j % len(A)])
		return cur_max


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		ansIfOne = kadane(A)
		ansIfTwo = sum(A) - kadaneMin(A[1:len(A) - 1])
		return max(ansIfOne, ansIfTwo)

def kadane(A):
	prevMax = -math.inf
	result = -math.inf
	for x in A:
		curMax = max(prevMax + x, x)
		prevMax = curMax
		result = max(result, curMax)
	return result

def kadaneMin(A):
	prevMin = math.inf
	result = math.inf
	for x in A:
		curMin = min(prevMin + x, x)
		prevMin = curMin
		result = min(result, curMin)
	return result


class Solution:

	def maxSubarraySumCircular1(self, A: List[int]) -> int:
		maxSubarraySum = [i for i in A]
		minSubarraySum = [i for i in A]
		for i in range(1, len(A)):
			maxSubarraySum[i] = max(maxSubarraySum[i - 1] + A[i], A[i])
		for i in range(1, len(A)):
			minSubarraySum[i] = min(minSubarraySum[i - 1] + A[i], A[i])
		return max(max(maxSubarraySum), sum(A) - min(minSubarraySum)) if max(maxSubarraySum) > 0 else max(maxSubarraySum)

	def maxSubarraySumCircular(self, A):
		total = 0
		curMax = 0
		maxSubArraySum = A[0]
		curMin = 0
		minSubArraySum = A[0]
		for a in A:
			curMax = max(curMax + a, a)
			maxSubArraySum = max(maxSubArraySum, curMax)
			curMin = min(curMin + a, a)
			minSubArraySum = min(minSubArraySum, curMin)
			total += a
		return max(maxSubArraySum, total - minSubArraySum) if maxSubArraySum > 0 else maxSubArraySum


import sys

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kadane(A, n):
			maxG = 0
			curr_max = 0
			for i in range(n):
				curr_max += A[i]
				curr_max = max(0, curr_max)
				maxG = max(maxG, curr_max)
			return maxG
		flag = None
		for i in A:
			if i > 0:
				flag = 1
				break
		if not flag:
			return max(A)
		n = len(A)
		noWrap = kadane(A, n)
		total = 0
		for i in range(n):
			total += A[i]
			A[i] *= -1
		minTotal = kadane(A, n)
		maxG = total + minTotal
		return max(noWrap, maxG)


class Solution:

	def maxSubarraySumCircular(self, A):

		def kadane(gen):
			ans = cur = float('-inf')
			for x in gen:
				cur = max(cur, 0) + x
				ans = max(ans, cur)
			return ans
		S = sum(A)
		ans1 = kadane(iter(A))
		ans2 = S + kadane((-A[i] for i in range(1, len(A))))
		ans3 = S + kadane((-A[i] for i in range(len(A) - 1)))
		return max(ans1, ans2, ans3)


class Solution:

	def maxSubarraySumCircular(self, arr: List[int]) -> int:
		max_eh = arr[0]
		min_eh = arr[0]
		max_sf = arr[0]
		min_sf = arr[0]
		total = sum(arr)
		for i in range(1, len(arr)):
			max_eh = max(max_eh + arr[i], arr[i])
			max_sf = max(max_eh, max_sf)
			min_eh = min(min_eh + arr[i], arr[i])
			min_sf = min(min_eh, min_sf)
		if min_sf == total:
			return max_sf
		else:
			return max(max_sf, total - min_sf)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		res = A[0]
		cur = A[0]
		sumn = sum(A)
		for num in A[1:]:
			cur = num + max(0, cur)
			res = max(cur, res)
		if len(A) >= 2:
			mincur = -A[1]
			minres = -A[1]
			for num in A[2:]:
				mincur = -num + max(0, mincur)
				minres = max(minres, mincur)
			res = max(res, sumn + minres)
			mincur = -A[0]
			minres = -A[0]
			for num in A[1:len(A) - 1]:
				mincur = -num + max(0, mincur)
				minres = max(minres, mincur)
			res = max(res, sumn + minres)
		return res


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		local_min = 0
		local_max = 0
		global_min = A[0]
		global_max = A[0]
		total = 0
		for num in A:
			total += num
			local_min = min(local_min + num, num)
			global_min = min(global_min, local_min)
			local_max = max(local_max + num, num)
			global_max = max(global_max, local_max)
		if global_max < 0:
			return global_max
		else:
			return max(global_max, total - global_min)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		max_sum = min_sum = A[0]
		curr_max = curr_min = tot = 0
		for a in A:
			curr_max = max(curr_max + a, a)
			curr_min = min(curr_min + a, a)
			max_sum = max(curr_max, max_sum)
			min_sum = min(curr_min, min_sum)
			tot += a
		return max(max_sum, tot - min_sum) if max_sum > 0 else max_sum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		maxsum = minsum = A[0]
		curmax = curmin = total = 0
		for num in A:
			curmax = max(num, curmax + num)
			maxsum = max(maxsum, curmax)
			curmin = min(num, curmin + num)
			minsum = min(minsum, curmin)
			total += num
		return max(maxsum, total - minsum) if maxsum > 0 else maxsum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		maxSubarraySum = [i for i in A]
		minSubarraySum = [i for i in A]
		for i in range(1, len(A)):
			maxSubarraySum[i] = max(maxSubarraySum[i - 1] + A[i], A[i])
		for i in range(1, len(A)):
			minSubarraySum[i] = min(minSubarraySum[i - 1] + A[i], A[i])
		return max(max(maxSubarraySum), sum(A) - min(minSubarraySum)) if max(maxSubarraySum) > 0 else max(maxSubarraySum)


class Solution:

	def maxSubarraySumCircular(self, A):
		n = len(A)
		S = sum(A)
		m1 = self.kadane(A)
		m2 = S + self.kadane([-A[i] for i in range(1, n)])
		m3 = S + self.kadane([-A[i] for i in range(n - 1)])
		return max(m1, m2, m3)

	def kadane(self, arr):
		res = cur = -float('inf')
		for a in arr:
			cur = a + max(0, cur)
			res = max(cur, res)
		return res


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		B = [0] + A + A
		for i in range(1, len(B)):
			B[i] += B[i - 1]
		maxv = B[1]
		stack = [0]
		for end in range(1, len(B)):
			num = B[end]
			while stack and num < B[stack[-1]]:
				stack.pop()
			stack.append(end)
			if end - stack[0] == n + 1:
				stack.pop(0)
			maxv = max(num - B[stack[0]], maxv)
		if all((x < 0 for x in A)):
			return max(A)
		return maxv


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if A == None or len(A) == 0:
			return 0
		(max_sum, min_sum, total) = (-100000000, 1000000000, 0)
		(curr_max_sum, curr_min_sum) = (0, 0)
		for i in A:
			curr_max_sum += i
			max_sum = max(curr_max_sum, max_sum)
			curr_max_sum = max(curr_max_sum, 0)
			curr_min_sum += i
			min_sum = min(curr_min_sum, min_sum)
			curr_min_sum = min(curr_min_sum, 0)
			total += i
		return max_sum if max_sum < 0 else max(max_sum, total - min_sum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		maxSum = A[0]
		minSum = A[0]
		currMax = 0
		currMin = 0
		total = 0
		for a in A:
			currMax = max(currMax + a, a)
			maxSum = max(currMax, maxSum)
			currMin = min(currMin + a, a)
			minSum = min(currMin, minSum)
			total += a
		return max(maxSum, total - minSum) if maxSum > 0 else maxSum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		max_seen = max(A)
		if max_seen < 0:
			return max_seen
		min_seen = float('inf')
		curr_max = 0
		curr_min = 0
		total = 0
		for num in A:
			total += num
			curr_max = max(0, curr_max + num)
			curr_min = min(0, curr_min + num)
			max_seen = max(max_seen, curr_max)
			min_seen = min(min_seen, curr_min)
		return max(max_seen, total - min_seen)


from sys import maxsize

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		i = 1
		n = len(A)
		ans = A[0]
		ans_max = A[0]
		ans_min = A[0]
		ans_f = A[0]
		sumi = A[0]
		while i < n:
			sumi += A[i]
			if ans + A[i % n] > A[i % n]:
				ans += A[i % n]
			else:
				ans = A[i % n]
			if ans_f + A[i % n] < A[i % n]:
				ans_f += A[i % n]
			else:
				ans_f = A[i % n]
			ans_max = max(ans_max, ans)
			ans_min = min(ans_min, ans_f)
			i += 1
		return max(ans_max, sumi - ans_min) if ans_min != sumi else ans_max


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		for i in range(1, len(A)):
			A[i] += A[i - 1]
		(pre_min, pre_max) = (float('inf'), float('-inf'))
		(res1, res2) = (A[0], A[0])
		for a in A:
			res1 = max(res1, a - pre_min)
			res2 = min(res2, a - pre_max)
			pre_min = min(pre_min, a)
			pre_max = max(pre_max, a)
		res1 = max(res1, A[-1])
		res2 = min(res2, A[-1])
		if res2 == A[-1]:
			return res1
		else:
			return max(res1, A[-1] - res2)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		if n == 1:
			return A[0]
		max_ = A[0]
		current = 0
		for num in A:
			current += num
			max_ = max(max_, current)
			if current < 0:
				current = 0
		max_from_left = [0] * n
		max_from_left[0] = float('-inf')
		current = A[0]
		for idx in range(1, n):
			max_from_left[idx] = max(max_from_left[idx - 1], current)
			current += A[idx]
		max_from_left[0] = 0
		so_far = 0
		for idx in range(n - 1, -1, -1):
			so_far += A[idx]
			max_ = max(max_, so_far + max_from_left[idx])
		return max_


import math

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		total = 0
		(maxss, maxss_cur) = (-math.inf, -math.inf)
		(minss, minss_cur) = (0, 0)
		for a in A:
			maxss_cur = a + max(maxss_cur, 0)
			maxss = max(maxss, maxss_cur)
			minss_cur = a + min(minss_cur, 0)
			minss = min(minss, minss_cur)
			total += a
		return maxss if total == minss else max(maxss, total - minss)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		currMaxSum = 0
		currMinSum = 0
		maxSum = float('-inf')
		minSum = float('inf')
		flag = False
		totalSum = 0
		for i in range(len(A)):
			currMaxSum += A[i]
			maxSum = max(maxSum, currMaxSum)
			if currMaxSum < 0:
				currMaxSum = 0
			totalSum += A[i]
			if A[i] >= 0:
				flag = True
			currMinSum += A[i]
			minSum = min(minSum, currMinSum)
			if currMinSum > 0:
				currMinSum = 0
		if flag:
			return max(totalSum - minSum, maxSum)
		else:
			return maxSum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if not A:
			return 0
		dp_max = [-99999] * len(A)
		dp_min = [-99999] * len(A)
		(dp_max[0], dp_min[0]) = (A[0], A[0])
		for i in range(1, len(A)):
			dp_max[i] = max(A[i], dp_max[i - 1] + A[i])
			dp_min[i] = min(A[i], dp_min[i - 1] + A[i])
		if min(dp_min) == sum(A):
			return max(dp_max)
		else:
			return max(max(dp_max), sum(A) - min(dp_min))


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		max_sum = -float('inf')
		cur_max = -float('inf')
		total_sum = 0
		cur_min = float('inf')
		min_sum = float('inf')
		for i in A:
			total_sum += i
			cur_max = max(cur_max + i, i)
			cur_min = min(cur_min + i, i)
			max_sum = max(max_sum, cur_max)
			min_sum = min(min_sum, cur_min)
		if total_sum - min_sum == 0:
			return max_sum
		return max(max_sum, total_sum - min_sum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if not A:
			return 0
		(max_sum, cur_max, min_sum, cur_min, total) = (A[0], 0, A[0], 0, 0)
		for a in A:
			cur_max = max(a + cur_max, a)
			max_sum = max(max_sum, cur_max)
			cur_min = min(a + cur_min, a)
			min_sum = min(min_sum, cur_min)
			total += a
		return max(max_sum, total - min_sum) if total > min_sum else max_sum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		total = sum(A)
		minSum = self.maxSum([-x for x in A]) + total
		maxSum = self.maxSum(A)
		return max(maxSum, minSum) if minSum > 0 else maxSum

	def maxSum(self, A: List[int]) -> int:
		current = 0
		max_sum = float('-inf')
		for num in A:
			current += num
			if current > max_sum:
				max_sum = current
			if current < 0:
				current = 0
		return max_sum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		maxSum = curSum = A[0]
		for i in range(1, len(A)):
			curSum = max(A[i], A[i] + curSum)
			maxSum = max(maxSum, curSum)
		if maxSum < 0:
			return maxSum
		minSum = curSum = A[0]
		for i in range(1, len(A)):
			curSum = min(A[i], A[i] + curSum)
			minSum = min(minSum, curSum)
		return max(sum(A) - minSum, maxSum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		total_sum = 0
		global_max = A[0]
		global_min = A[0]
		local_max = 0
		local_min = 0
		for num in A:
			local_max = max(num, local_max + num)
			local_min = min(num, local_min + num)
			global_max = max(global_max, local_max)
			global_min = min(global_min, local_min)
			total_sum += num
		circular_max = total_sum - global_min
		if global_max <= 0:
			return global_max
		return max(circular_max, global_max)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		SUM = 0
		MIN = 0
		minsum = sys.maxsize
		MAX = 0
		maxsum = -sys.maxsize
		for num in A:
			SUM += num
			maxsum = max(maxsum, SUM - MIN)
			MIN = min(MIN, SUM)
			minsum = min(minsum, SUM - MAX)
			MAX = max(MAX, SUM)
		if minsum == SUM:
			return maxsum
		return max(maxsum, SUM - minsum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		if n == 1:
			return A[0]
		global_max = float('-inf')
		global_min = float('inf')
		local_max = 0
		local_min = 0
		for (i, a) in enumerate(A):
			local_max = max(local_max + a, a)
			global_max = max(global_max, local_max)
			if 0 < i < n - 1:
				local_min = min(local_min + a, a)
				global_min = min(global_min, local_min)
		return max(global_max, sum(A) - global_min)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		max1 = -float('inf')
		maxc = -float('inf')
		for i in range(len(A)):
			maxc = max(maxc + A[i], A[i])
			max1 = max(max1, maxc)
		min1 = float('inf')
		minc = float('inf')
		for i in range(len(A)):
			minc = min(minc + A[i], A[i])
			min1 = min(min1, minc)
		if min1 == sum(A):
			return max1
		return max(max1, sum(A) - min1)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		max_sub_ending = [A[0]]
		max_sub_ending_index = [0]
		for i in range(1, len(A)):
			prev = max_sub_ending[i - 1]
			if prev <= 0:
				max_sub_ending_index.append(i)
				max_sub_ending.append(A[i])
			else:
				max_sub_ending_index.append(max_sub_ending_index[-1])
				max_sub_ending.append(A[i] + max_sub_ending[-1])
		print(max_sub_ending)
		posmax = max(max_sub_ending)
		total = sum(A)
		for i in range(len(A)):
			A[i] = -A[i]
		max_sub_ending = [A[0]]
		max_sub_ending_index = [0]
		for i in range(1, len(A)):
			prev = max_sub_ending[i - 1]
			if prev <= 0:
				max_sub_ending_index.append(i)
				max_sub_ending.append(A[i])
			else:
				max_sub_ending_index.append(max_sub_ending_index[-1])
				max_sub_ending.append(A[i] + max_sub_ending[-1])
		print(max_sub_ending)
		negmax = max(max_sub_ending) + total
		if negmax > posmax and negmax != 0:
			return negmax
		else:
			return posmax


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		total = A[0]
		curmax = A[0]
		curmin = A[0]
		maxsum = curmax
		minsum = curmin
		for i in range(1, n):
			curmax = max(curmax + A[i], A[i])
			maxsum = max(maxsum, curmax)
			curmin = min(curmin + A[i], A[i])
			minsum = min(minsum, curmin)
			total += A[i]
		if total == minsum:
			return maxsum
		else:
			return max(maxsum, total - minsum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		maxSum = -float('inf')
		currSum = 0
		for j in range(n):
			ele = A[j]
			newSum = currSum + ele
			maxSum = max(maxSum, newSum)
			if currSum > 0 and newSum < 0:
				currSum = 0
			elif currSum <= 0 and newSum < currSum:
				currSum = 0
			else:
				currSum = newSum
		lSum = 0
		bestLSum = 0
		totalSum = sum(A)
		for i in range(n):
			currSum = totalSum - lSum
			currSum += bestLSum
			maxSum = max(maxSum, currSum)
			lSum += A[i]
			bestLSum = max(lSum, bestLSum)
		return maxSum


class Solution:

	def maxSubarraySumCircular(self, arr: List[int]) -> int:

		def maxsub(a, n):
			maxsum = a[0]
			currsum = 0
			for i in range(n):
				if currsum + a[i] > 0:
					currsum += a[i]
					maxsum = max(maxsum, currsum)
				else:
					currsum = 0
					maxsum = max(maxsum, a[i])
			return maxsum
		b = [i * -1 for i in arr]
		n = len(arr)
		s = sum(arr)
		ans2 = 0
		ans2 = maxsub(b, n)
		if s == -ans2:
			ans2 = -ans2
		return max(maxsub(arr, n), s + ans2)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if len(A) == 0:
			return 0
		minS = minT = maxS = maxT = s = A[0]
		for i in range(1, len(A)):
			minS = min(A[i], minS + A[i])
			minT = min(minS, minT)
			maxS = max(A[i], maxS + A[i])
			maxT = max(maxT, maxS)
			s += A[i]
		if s == minT:
			return maxT
		return max(s - minT, maxT)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if len(A) == 1:
			return A[0]
		s = sum(A)
		nums = A
		m = nums[0]
		last = m
		num = 1
		last_max = m
		res = last
		res_max = last_max
		for i in A[1:]:
			if i + last < i:
				last = i + last
				num += 1
			else:
				last = i
				num = 1
			if num != len(A):
				res = min(res, last)
			last_max = max(i, i + last_max)
			res_max = max(res_max, last_max)
		return max(s - res, res_max)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		currentMax = totalMax = currentMin = totalMin = A[0]
		s = A[0]
		for i in range(1, len(A)):
			currentMax = max(currentMax + A[i], A[i])
			totalMax = max(totalMax, currentMax)
			currentMin = min(currentMin + A[i], A[i])
			totalMin = min(totalMin, currentMin)
			s += A[i]
		if s - totalMin != 0:
			return max(totalMax, s - totalMin)
		else:
			return totalMax


import math
import random
import string
from functools import lru_cache
from operator import truediv
from typing import List, Set
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
import numpy as np
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

class Solution:

	def maxSubarraySumCircular(self, A):
		(total, maxSum, curMax, minSum, curMin) = (0, A[0], 0, A[0], 0)
		for a in A:
			curMax = max(curMax + a, a)
			maxSum = max(maxSum, curMax)
			curMin = min(curMin + a, a)
			minSum = min(minSum, curMin)
			total += a
		return max(maxSum, total - minSum) if maxSum > 0 else maxSum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		dp = [0] * n
		optsum = [A[0]] * n
		pre = A[0]
		dp[0] = A[0]
		first = dp[0]
		for i in range(1, n):
			dp[i] = max(dp[i - 1] + A[i], A[i])
			first = max(first, dp[i])
			pre += A[i]
			if pre > optsum[i - 1]:
				optsum[i] = pre
			else:
				optsum[i] = optsum[i - 1]
		pre = 0
		for j in range(n - 1, 0, -1):
			first = max(first, pre + A[j] + optsum[j - 1])
			pre += A[j]
		return first


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		ans1 = cur = 0
		for x in A:
			cur = x + max(cur, 0)
			ans1 = max(ans1, cur)
		ans2 = cur = 0
		for x in A[1:]:
			cur = x + min(cur, 0)
			ans2 = min(ans2, cur)
		ans2 = sum(A) - ans2
		ans3 = cur = 0
		for x in A[:-1]:
			cur = x + min(cur, 0)
			ans3 = min(ans3, cur)
		ans3 = sum(A) - ans3
		ans = max(ans1, ans2, ans3)
		return ans if ans != 0 else max(A)


class Solution:

	def maxSubarraySumCircular(self, nums: List[int]) -> int:
		greatest: int = -sys.maxsize + 1
		smallest: int = sys.maxsize
		x = y = total = 0
		for i in range(len(nums)):
			x += nums[i]
			greatest = max(greatest, x)
			x = max(x, 0)
			y += nums[i]
			smallest = min(smallest, y)
			y = min(y, 0)
			total += nums[i]
		return greatest if greatest < 0 else max(greatest, total - smallest)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		ans = cur = 0
		for x in A:
			cur = x + max(cur, 0)
			ans = max(ans, cur)
		rightsums = [None] * N
		rightsums[-1] = A[-1]
		for i in range(N - 2, -1, -1):
			rightsums[i] = rightsums[i + 1] + A[i]
		maxright = [None] * N
		maxright[-1] = rightsums[-1]
		for i in range(N - 2, -1, -1):
			maxright[i] = max(maxright[i + 1], rightsums[i])
		leftsum = 0
		for i in range(N - 2):
			leftsum += A[i]
			ans = max(ans, leftsum + maxright[i + 1])
		if max(A) < 0:
			return max(A)
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		sums = sum(A)
		min_res = min_s = sys.maxsize
		max_res = max_s = -sys.maxsize
		n = len(A)
		for i in range(n):
			min_s = min(A[i], min_s + A[i])
			max_s = max(A[i], max_s + A[i])
			min_res = min(min_res, min_s)
			max_res = max(max_res, max_s)
		if min_res == sums:
			min_res = min(A)
		else:
			min_res = sums - min_res
		return max(min_res, max_res)


import numpy as np

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		(total, maxSum, curMax, minSum, curMin) = (0, A[0], -np.Infinity, A[0], np.Infinity)
		for a in A:
			curMax = max(curMax + a, a)
			maxSum = max(maxSum, curMax)
			curMin = min(curMin + a, a)
			minSum = min(minSum, curMin)
			total += a
		return max(maxSum, total - minSum) if maxSum > 0 else maxSum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		if max(A) <= 0:
			return max(A)
		endmax = [i for i in A]
		endmin = [i for i in A]
		for i in range(len(A) - 1):
			if endmax[i] > 0:
				endmax[i + 1] += endmax[i]
			if endmin[i] < 0:
				endmin[i + 1] += endmin[i]
		return max(max(endmax), sum(A) - min(endmin))


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kadane(gen):
			ans = None
			cur = None
			for x in gen:
				if cur:
					cur = x + max(cur, 0)
				else:
					cur = x
				if ans:
					ans = max(ans, cur)
				else:
					ans = cur
			return ans
		S = sum(A)
		ans1 = kadane(A)
		if len(A) > 1:
			ans2 = S + kadane([-A[i] for i in range(1, len(A))])
			ans3 = S + kadane([-A[i] for i in range(len(A) - 1)])
			return max(ans1, ans2, ans3)
		else:
			return ans1


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		ans = cur = float('-inf')
		for x in A:
			cur = x + max(cur, 0)
			ans = max(ans, cur)
		rightsums = [0] * n
		rightsums[-1] = A[-1]
		for i in range(n - 2, -1, -1):
			rightsums[i] = rightsums[i + 1] + A[i]
		maxright = [0] * n
		maxright[-1] = rightsums[-1]
		for i in range(n - 2, -1, -1):
			maxright[i] = max(maxright[i + 1], rightsums[i])
		leftsum = 0
		for i in range(n - 2):
			leftsum += A[i]
			ans = max(ans, leftsum + maxright[i + 2])
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kadane(A):
			ts = A[0]
			ms = A[0]
			for i in range(1, len(A)):
				ts = max(A[i], ts + A[i])
				ms = max(ms, ts)
			return ms
		x = kadane(A)
		for i in range(len(A)):
			A[i] *= -1
		s = sum(A)
		y = kadane(A)
		if y == s:
			y = -10000000000.0
		else:
			y = -s + y
		return max(x, y)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def find_max_sum(A):
			curr_sum = 0
			max_sum = -math.inf
			for num in A:
				if curr_sum > 0:
					curr_sum += num
				else:
					curr_sum = num
				max_sum = max(max_sum, curr_sum)
			return max_sum
		max_sum = find_max_sum(A)
		min_sum_1 = -find_max_sum((-num for num in A[1:]))
		min_sum_2 = -find_max_sum((-num for num in A[:-1]))
		return max(sum(A) - min(min_sum_1, min_sum_2), max_sum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		A *= 2
		ans = [0] * len(A)
		q = collections.deque()
		cur = 0
		for (i, a) in enumerate(A):
			while q and i - q[0][0] > n:
				q.popleft()
			cur += a
			ans[i] = cur - q[0][1] if q else cur
			while q and q[-1][1] >= cur:
				q.pop()
			q.append((i, cur))
		return max(ans)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kadane(gen):
			ans = -sys.maxsize
			cur = -sys.maxsize
			for x in gen:
				cur = x + max(cur, 0)
				ans = max(ans, cur)
			return ans
		S = sum(A)
		ans1 = kadane(iter(A))
		ans2 = S + kadane((-A[i] for i in range(1, len(A))))
		ans3 = S + kadane((-A[i] for i in range(len(A) - 1)))
		return max(ans1, ans2, ans3)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kaden(gen):
			ans = cur = gen[0]
			for n in gen[1:]:
				cur = n + max(0, cur)
				ans = max(ans, cur)
			return ans
		ans1 = kaden(A)
		if len(A) > 1:
			s = sum(A)
			ans2 = s + kaden([-a for a in A[1:]])
			ans3 = s + kaden([-a for a in A[:-1]])
		else:
			ans2 = ans3 = -float('inf')
		return max(ans1, ans2, ans3)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		B = A.copy()
		for i in range(1, len(B)):
			if B[i - 1] > 0:
				B[i] += B[i - 1]
		maxsum = max(B)
		C = A.copy()
		for i in range(1, len(C)):
			if C[i - 1] < 0:
				C[i] += C[i - 1]
		minsum = min(C)
		if minsum == sum(A):
			return max([maxsum, max(A)])
		return max([maxsum, sum(A) - minsum])


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		ans = cur = float('-inf')
		for v in A:
			cur = v + max(cur, 0)
			ans = max(ans, cur)
		rightsum = [0] * n
		rightsum[-1] = A[-1]
		for i in range(n - 2, -1, -1):
			rightsum[i] = rightsum[i + 1] + A[i]
		rightmax = [0] * n
		rightmax[-1] = rightsum[-1]
		for i in range(n - 2, -1, -1):
			rightmax[i] = max(rightmax[i + 1], rightsum[i])
		cur = 0
		for i in range(n - 2):
			cur += A[i]
			ans = max(ans, cur + rightmax[i + 2])
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		ans = -float('inf')
		currmax = -float('inf')
		for i in range(n):
			currmax = max(currmax + A[i], A[i])
			ans = max(ans, currmax)
		right_sums = [0] * n
		right_sums[-1] = A[-1]
		for i in range(1, n):
			right_sums[n - 1 - i] = right_sums[n - i] + A[n - i - 1]
		maxright = [0] * n
		maxright[-1] = right_sums[-1]
		for i in range(1, n):
			maxright[n - i - 1] = max(maxright[n - i], right_sums[n - i - 1])
		lefts = 0
		for i in range(n - 2):
			lefts += A[i]
			ans = max(ans, lefts + maxright[i + 2])
		return ans


class Solution:

	def maxSubarraySumCircular(self, A):
		total = sum(A)
		max_sum = [0 for i in range(len(A))]
		min_sum = [0 for i in range(len(A))]
		max_sum[0] = A[0]
		min_sum[0] = A[0]
		best_non_loop = max_sum[0]
		best_inverse_loop = min_sum[0]
		for i in range(1, len(A)):
			max_sum[i] = A[i] + max(max_sum[i - 1], 0)
			min_sum[i] = A[i] + min(min_sum[i - 1], 0)
			best_non_loop = max(best_non_loop, max_sum[i])
			best_inverse_loop = min(best_inverse_loop, min_sum[i])
		ret = max(best_non_loop, total - best_inverse_loop)
		if ret == 0:
			return max(A)
		return ret


class Solution(object):

	def maxSubarraySumCircular(self, A):
		N = len(A)
		P = [0]
		for _ in range(2):
			for x in A:
				P.append(P[-1] + x)
		ans = A[0]
		deque = collections.deque([0])
		for j in range(1, len(P)):
			if deque[0] < j - N:
				deque.popleft()
			ans = max(ans, P[j] - P[deque[0]])
			while deque and P[j] <= P[deque[-1]]:
				deque.pop()
			deque.append(j)
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		tot = sum(A)
		B = A[:]
		for i in range(1, len(A)):
			if A[i - 1] > 0:
				A[i] += A[i - 1]
			if B[i - 1] < 0:
				B[i] += B[i - 1]
		submax = max(A)
		submin = min(B)
		return max(submax, tot - submin) if tot != submin else submax


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		prefix = [0]
		for _ in range(2):
			for x in A:
				prefix.append(prefix[-1] + x)
		res = A[0]
		deque = collections.deque([0])
		for j in range(1, len(prefix)):
			if deque[0] < j - N:
				deque.popleft()
			res = max(res, prefix[j] - prefix[deque[0]])
			while deque and prefix[j] <= prefix[deque[-1]]:
				deque.pop()
			deque.append(j)
		return res


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		maxHere = currentMax = float('-inf')
		minHere = currentMin = float('inf')
		for i in A:
			currentMax = i + max(0, currentMax)
			currentMin = i + min(0, currentMin)
			maxHere = max(currentMax, maxHere)
			minHere = min(currentMin, minHere)
		print(maxHere, minHere)
		if minHere == sum(A) and 0 not in A:
			return maxHere
		return max(maxHere, sum(A) - minHere)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		l = len(A)
		A = A + A
		q = collections.deque([(0, -1)])
		cur = 0
		ret = float('-inf')
		for (i, num) in enumerate(A):
			cur += num
			ret = max(ret, cur - q[0][0])
			if q[0][1] + l == i:
				q.popleft()
			while len(q) > 0 and q[-1][0] > cur:
				q.pop()
			q.append((cur, i))
		return ret


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def kadane(aa):
			ans = cur = float('-inf')
			for v in aa:
				cur = max(cur, 0) + v
				ans = max(ans, cur)
			return ans
		S = sum(A)
		ans1 = kadane(A)
		ans2 = S + kadane((-A[i] for i in range(1, len(A))))
		ans3 = S + kadane((-A[i] for i in range(len(A) - 1)))
		return max(ans1, ans2, ans3)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		L = len(A)
		cum_sum = [0] * L
		cum_max = [0] * L
		cum_max_final = [0] * L
		sum_ = 0
		for i in range(L):
			sum_ += A[i]
			cum_sum[i] = sum_
			if i == 0:
				cum_max[i] = A[i]
			elif cum_max[i - 1] > 0:
				cum_max[i] = cum_max[i - 1] + A[i]
			else:
				cum_max[i] = A[i]
		m = A[L - 1]
		for i in range(L - 1, -1, -1):
			if i != 0:
				cur = cum_sum[L - 1] - cum_sum[i - 1]
				cum_max_final[i] = max(cur, m)
				m = max(m, cur)
			else:
				cum_max_final[i] = max(m, cum_sum[L - 1])
		res = -float('inf')
		for i in range(L):
			if i != L - 1:
				cur = cum_max[i]
				cur = max(cur, cum_sum[i] + cum_max_final[i + 1])
				res = max(res, cur)
			else:
				res = max(res, cum_max[L - 1])
		return res


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		pre = 0
		rtn = float('-inf')
		if max(A) <= 0:
			return max(A)
		for i in range(len(A)):
			pre += A[i]
			if pre <= 0:
				pre = 0
			else:
				rtn = max(rtn, pre)
		left_sum = [0] * (len(A) + 1)
		left = 0
		for i in range(len(A)):
			left += A[i]
			left_sum[i + 1] = max(left, left_sum[i])
		right = 0
		for j in reversed(range(len(A))):
			right += A[j]
			rtn = max(rtn, right + left_sum[j])
		return rtn


class Solution:

	def maxSubarraySumCircular(self, A):
		pre = [0 for i in range(len(A))]
		pre_continuous = [0 for i in range(len(A))]
		pre_earlystop = [0 for i in range(len(A))]
		for i in range(len(A) - 2, -1, -1):
			pre_continuous[i] = pre_continuous[i + 1] + A[i + 1]
			pre_earlystop[i] = max(pre_earlystop[i + 1], pre_continuous[i])
			pre[i] = max(pre_continuous[i], pre_earlystop[i])
		dp = [0 for i in range(len(A))]
		dp[0] = A[0]
		running_sum = A[0]
		best = dp[0] + pre[0]
		for i in range(1, len(A)):
			dp[i] = max(dp[i - 1] + A[i], A[i])
			best = max(best, dp[i], running_sum + pre[i])
			running_sum += A[i]
		return best


from collections import deque

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		B = A + A
		N = len(A)
		queue = deque([0])
		pre_sum = [0]
		for i in range(len(B)):
			pre_sum.append(pre_sum[-1] + B[i])
		ans = A[0]
		for j in range(1, len(pre_sum)):
			if j - queue[0] > N:
				queue.popleft()
			ans = max(ans, pre_sum[j] - pre_sum[queue[0]])
			while queue and pre_sum[queue[-1]] >= pre_sum[j]:
				queue.pop()
			queue.append(j)
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		negateA = [-x for x in A]
		print(negateA)
		cursum = 0
		res = float('-inf')
		for v in negateA:
			cursum = max(v, cursum + v)
			res = max(res, cursum)
		print(res)
		res1 = float('-inf')
		cursum = 0
		for v in A:
			cursum = max(v, cursum + v)
			res1 = max(res1, cursum)
		print(res1)
		return max(res1, sum(A) + res) if res1 > 0 else res1


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		ans = float('-inf')
		csum = 0
		for x in A:
			csum = max(x, csum + x)
			ans = max(ans, csum)
		mi = float('inf')
		csum = 0
		for i in range(1, len(A) - 1):
			csum = min(csum + A[i], A[i])
			mi = min(mi, csum)
		ans = max(ans, sum(A) - mi)
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		P = [0]
		for _ in range(2):
			for v in A:
				P.append(P[-1] + v)
		ans = A[0]
		q = collections.deque([0])
		for j in range(1, len(P)):
			while q and j - q[0] > N:
				q.popleft()
			ans = max(ans, P[j] - P[q[0]])
			while q and P[q[-1]] >= P[j]:
				q.pop()
			q.append(j)
		return ans


from collections import deque

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		arr = A + A
		arr = arr[:-1]
		prefix = [0] * len(arr)
		prefix[0] = arr[0]
		for i in range(1, len(prefix)):
			prefix[i] = prefix[i - 1] + arr[i]
		prefix.insert(0, 0)
		dq = deque([0])
		res = -float('inf')
		for i in range(1, len(prefix)):
			while dq and i - dq[0] > len(A):
				dq.popleft()
			if dq:
				res = max(res, prefix[i] - prefix[dq[0]])
			while dq and prefix[i] <= prefix[dq[-1]]:
				dq.pop()
			dq.append(i)
		return res


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		if n == 1:
			return A[0]
		pre_sum = 0
		pre_min_sum = 0
		pre_max_sum = 0
		pre_max_sum_i = -1
		min_sum_left = -1
		min_sum_right = -1
		max_sum = float('-inf')
		min_sum = float('inf')
		for (i, a) in enumerate(A):
			pre_sum += a
			max_sum = max(max_sum, pre_sum - pre_min_sum)
			min_sum_tmp = pre_sum - pre_max_sum
			if min_sum_tmp < min_sum:
				min_sum = min_sum_tmp
				min_sum_right = i
				min_sum_left = pre_max_sum_i + 1
			pre_min_sum = min(pre_min_sum, pre_sum)
			if pre_sum > pre_max_sum:
				pre_max_sum = pre_sum
				pre_max_sum_i = i
		total = sum(A)
		if total == min_sum and min_sum_left == 0 and (min_sum_right == n - 1):
			return max_sum
		return max(max_sum, total - min_sum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		from collections import deque
		dq = deque()
		prefix = [0]
		N = len(A)
		for _ in range(2):
			for elem in A:
				prefix.append(elem + prefix[-1])
		result = A[0]
		for i in range(len(prefix)):
			if dq and dq[0] < i - N:
				dq.popleft()
			if dq:
				result = max(result, prefix[i] - prefix[dq[0]])
			while dq and prefix[dq[-1]] > prefix[i]:
				dq.pop()
			dq.append(i)
		return result


from copy import deepcopy

def cumsum(A: list) -> list:
	cum = 0
	res = []
	for x in A:
		cum += x
		res.append(cum)
	return res

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		opt = deepcopy(A)
		n = len(A)
		for i in range(1, n, 1):
			if opt[i - 1] + A[i] > opt[i]:
				opt[i] = opt[i - 1] + A[i]
		forward_cumsum = cumsum(A)
		back_cumsum = cumsum(A[::-1])
		tmp = [back_cumsum[0]]
		for i in range(1, n):
			tmp.append(max(tmp[i - 1], back_cumsum[i]))
		back_cumsum = tmp
		for i in range(0, n - 1):
			potential_replacement = forward_cumsum[i] + back_cumsum[n - 2 - i]
			opt[i] = max(opt[i], potential_replacement)
		return max(opt)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		max_sums_left = []
		max_sums_right = collections.deque()
		sum_up_to_index = []
		max_sums_index_right = collections.deque()
		min_sum_right = 0
		min_sum_left = 0
		max_sum_right = 0
		max_sum_left = 0
		sum_left = 0
		sum_right = 0
		ret = -999999999
		for i in range(len(A)):
			sum_left += A[i]
			sum_right += A[-i - 1]
			sum_up_to_index.append(sum_left)
			max_sums_left.append(sum_left - min_sum_left)
			max_sums_right.appendleft(sum_right - min_sum_right)
			if sum_left < min_sum_left:
				min_sum_left = sum_left
			if sum_right > max_sum_right:
				max_sums_index_right.appendleft((len(A) - i - 1, sum_right))
				max_sum_right = sum_right
			elif sum_right < min_sum_right:
				min_sum_right = sum_right
			else:
				pass
		sum_left = 0
		for i in range(len(A)):
			if len(max_sums_index_right) and i == max_sums_index_right[0][0]:
				max_sums_index_right.popleft()
			sum_left += A[i]
			candidates = [max_sums_left[i] + max_sums_right[i] - A[i], sum_right + max_sum_left]
			sum_right -= A[i]
			if sum_left > max_sum_left:
				max_sum_left = sum_left
			if len(max_sums_index_right):
				candidates.append(sum_left + max_sums_index_right[0][1])
			candidate = max(candidates)
			if candidate > ret:
				ret = candidate
		return ret


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		n = len(A)
		B = A + A
		pfx = [0]
		for x in B:
			pfx.append(pfx[-1] + x)
		dq = collections.deque()
		ans = A[0]
		dq.append(0)
		for j in range(1, len(pfx)):
			if j - dq[0] > n:
				dq.popleft()
			ans = max(ans, pfx[j] - pfx[dq[0]])
			while dq and pfx[dq[-1]] > pfx[j]:
				dq.pop()
			dq.append(j)
		return ans


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def max_subarray(nums):
			for i in range(1, len(nums)):
				if nums[i - 1] > 0:
					nums[i] += nums[i - 1]
			return max(nums)
		(max_sum, cur_sum) = (max_subarray(A[:]), sum(A))
		if max_sum < 0:
			return max_sum
		final_sum = cur_sum + max_subarray(list(map(lambda x: -x, A)))
		return max(max_sum, final_sum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		allNeg = True
		for i in A:
			if i > 0:
				allNeg = False
		if allNeg:
			return max(A)
		maxSum = A[0]
		curMaxSum = A[0]
		for i in range(1, len(A)):
			curMaxSum = max(curMaxSum + A[i], A[i])
			maxSum = max(maxSum, curMaxSum)
		minSum = A[0]
		curMinSum = A[0]
		for i in range(1, len(A)):
			curMinSum = min(curMinSum + A[i], A[i])
			minSum = min(minSum, curMinSum)
		return max(maxSum, sum(A) - minSum)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		res = A[0]
		cur = A[0]
		for num in A[1:]:
			cur = num + max(0, cur)
			res = max(cur, res)
		presum = []
		accu = 0
		for num in A:
			accu += num
			presum.append(accu)
		postsum = [0 for i in range(len(A))]
		postsum[-1] = A[-1]
		accu = A[-1]
		curmax = A[-1]
		for i in range(len(A) - 2, -1, -1):
			accu += A[i]
			curmax = max(curmax, accu)
			postsum[i] = curmax
		for i in range(0, len(A) - 2):
			res = max(presum[i] + postsum[i + 2], res)
		return res


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		total = 0
		maxSum = A[0]
		minSum = A[0]
		curr_sum = 0
		curr_sum_min = 0
		for val in A:
			total += val
			curr_sum = max(val, curr_sum + val)
			maxSum = max(maxSum, curr_sum)
			curr_sum_min = min(val, curr_sum_min + val)
			minSum = min(minSum, curr_sum_min)
			print(maxSum)
		wrap_maxSum = total - minSum
		if maxSum > 0:
			return max(wrap_maxSum, maxSum)
		else:
			return maxSum


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		tot = 0
		(mn, mx) = (float('inf'), float('-inf'))
		(curmx, curmn) = (0, 0)
		for num in A:
			curmn = min(curmn + num, num)
			mn = min(mn, curmn)
			curmx = max(curmx + num, num)
			mx = max(mx, curmx)
			tot += num
		if tot == mn:
			return mx
		return max(mx, tot - mn)


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:

		def maxSum(gen):
			res = cur = -float('inf')
			for n in gen:
				cur = n + max(0, cur)
				res = max(res, cur)
			return res
		total = sum(A)
		res1 = maxSum(iter(A))
		res2 = total + maxSum((-A[i] for i in range(1, len(A))))
		res3 = total + maxSum((-A[i] for i in range(len(A) - 1)))
		return max(res1, res2, res3)


import heapq

class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		best = A[0]
		heap = [(0, -1)]
		current_sum = 0
		for i in range(2 * N):
			current_sum += A[i % N]
			while len(heap) > 0 and i - heap[0][1] > N:
				heapq.heappop(heap)
			best = max(best, current_sum - heap[0][0])
			heapq.heappush(heap, (current_sum, i))
		return best


class Solution:

	def maxSubarraySumCircular(self, A: List[int]) -> int:
		N = len(A)
		P = []
		P.append(0)
		for _ in range(2):
			for x in A:
				P.append(P[-1] + x)
		ans = A[0]
		queue = []
		queue.append(0)
		for j in range(1, len(P)):
			if queue[0] < j - N:
				queue.pop(0)
			ans = max(ans, P[j] - P[queue[0]])
			while queue and P[j] <= P[queue[-1]]:
				queue.pop()
			queue.append(j)
		return ans