Given an array arr[] of N integers arranged in a circular fashion. Your task is to find the maximum contiguous subarray sum.
Example 1:
Input:
N = 7
arr[] = {8,-8,9,-9,10,-11,12}
Output:
22
Explanation:
Starting from the last element
of the array, i.e, 12, and 
moving in a circular fashion, we 
have max subarray as 12, 8, -8, 9, 
-9, 10, which gives maximum sum 
as 22.
Example 2:
Input:
N = 8
arr[] = {10,-3,-4,7,6,5,-4,-1}
Output:
23
Explanation: Sum of the circular 
subarray with maximum sum is 23
Your Task:
The task is to complete the function circularSubarraySum() which returns a sum of the circular subarray with maximum sum.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{6}
-10^{6 }<= Arr[i] <= 10^{6}

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

#Complete this function
#Function to find maximum circular subarray sum.
def circularSubarraySum(arr,n):
    ##Your code here

Solutions:
def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	total_sum = sum(arr)
	maxsum = arr[0]
	currmax = arr[0]
	for i in range(1, n):
		currmax = max(currmax + arr[i], arr[i])
		maxsum = max(maxsum, currmax)
	minsum = arr[0]
	currmin = arr[0]
	for i in range(1, n):
		currmin = min(currmin + arr[i], arr[i])
		minsum = min(minsum, currmin)
	if minsum == total_sum:
		return maxsum
	return max(maxsum, total_sum - minsum)


def circularSubarraySum(arr, n):
	total = sum(arr)
	sum1 = 0
	ans_straight = -10000000000
	for i in arr:
		sum1 = max(i, sum1 + i)
		ans_straight = max(ans_straight, sum1)
	if ans_straight < 0:
		return ans_straight
	sum2 = 0
	min_sum = 1000000000
	for i in arr:
		sum2 = min(i, sum2 + i)
		min_sum = min(min_sum, sum2)
	ans_circular = -10000000000
	ans_circular = total - min_sum
	return max(ans_circular, ans_straight)


def circularSubarraySum(arr, n):
	ans1 = -float('inf')
	tans1 = -float('inf')
	ans2 = -float('inf')
	tans2 = -float('inf')
	s = 0
	for i in arr:
		tans1 = max(tans1 + i, i)
		ans1 = max(ans1, tans1)
		i *= -1
		tans2 = max(tans2 + i, i)
		ans2 = max(ans2, tans2)
		s += i
	if ans1 < 0:
		return ans1
	return max(-s + ans2, ans1)


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	max_sum = arr[0]
	current_max = arr[0]
	for i in range(1, n):
		current_max = max(arr[i], current_max + arr[i])
		max_sum = max(max_sum, current_max)
	if max_sum < 0:
		return max(arr)
	array_sum = sum(arr)
	max_wrap_sum = array_sum
	current_max = 0
	for i in range(n):
		current_max = min(arr[i], current_max + arr[i])
		max_wrap_sum = min(max_wrap_sum, current_max)
	max_circular_sum = max(max_sum, array_sum - max_wrap_sum)
	return max_circular_sum


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	max_sum = arr[0]
	curr_max_sum = arr[0]
	min_sum = arr[0]
	curr_min_sum = arr[0]
	total = arr[0]
	for num in arr[1:]:
		curr_max_sum = max(curr_max_sum + num, num)
		max_sum = max(curr_max_sum, max_sum)
		curr_min_sum = min(curr_min_sum + num, num)
		min_sum = min(curr_min_sum, min_sum)
		total = total + num
	if max_sum < 0:
		return max(arr)
	final_sum = max(max_sum, total - min_sum)
	return final_sum


def circularSubarraySum(array, n):
	if n == 0:
		return 0
	x = 1
	result = 100000
	tracker = -100000
	for i in range(n):
		if tracker < array[i] and array[i] < 0:
			tracker = array[i]
		if array[i] >= 0:
			x = 0
			break
		result = max(result, array[i])
	if x:
		return tracker
	result_1 = maxSumSubarray(array, n)
	array_sum = 0
	for i in range(n):
		array_sum += array[i]
	result_2 = array_sum - minSumSubarray(array, n)
	result = max(result_1, result_2)
	return result

def minSumSubarray(array, n):
	minimum_sum = 100000
	current_sum = 0
	for i in range(n):
		current_sum += array[i]
		minimum_sum = min(minimum_sum, current_sum)
		if current_sum > 0:
			current_sum = 0
	return minimum_sum

def maxSumSubarray(array, n):
	maximum_sum = -100000
	current_sum = 0
	for i in range(n):
		current_sum += array[i]
		maximum_sum = max(maximum_sum, current_sum)
		if current_sum < 0:
			current_sum = 0
	return maximum_sum


def normalsum(arr, n):
	maxsum = -99999999
	sum = 0
	for i in range(n):
		sum += arr[i]
		if sum > maxsum:
			maxsum = max(maxsum, sum)
		if sum < 0:
			sum = 0
	return maxsum

def circularSubarraySum(arr, n):
	nsum = arr[0]
	circuSum = arr[0]
	if n > 1:
		nsum = normalsum(arr, n)
		if nsum < 0:
			return nsum
		csum = 0
		for i in range(n):
			csum += arr[i]
			arr[i] = -arr[i]
		circuSum = csum + normalsum(arr, n)
	result = max(nsum, circuSum)
	return result


def circularSubarraySum(arr, n):
	(max_so_far, max_ending_here) = (arr[0], arr[0])
	for i in range(1, n):
		max_ending_here = max(arr[i], max_ending_here + arr[i])
		max_so_far = max(max_so_far, max_ending_here)
	total_sum = sum(arr)
	arr_inv = [-x for x in arr]
	max_wrap = total_sum + kadane(arr_inv)
	return max_wrap if max_wrap > max_so_far and max_wrap != 0 else max_so_far

def kadane(arr):
	(max_so_far, max_ending_here) = (arr[0], arr[0])
	for i in range(1, len(arr)):
		max_ending_here = max(arr[i], max_ending_here + arr[i])
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far


def circularSubarraySum(arr, n):

	def kadane(num):
		sumtillnow = num[0]
		totalsum = num[0]
		for i in num[1:]:
			sumtillnow = max(i, sumtillnow + i)
			totalsum = max(totalsum, sumtillnow)
		return totalsum
	t = kadane(arr)
	sum1 = 0
	for i in range(n):
		sum1 += arr[i]
		arr[i] = -arr[i]
	sum1 += kadane(arr)
	if sum1 > t and sum1 != 0:
		return sum1
	else:
		return t


def circularSubarraySum(arr, n):
	end = 1
	kadane_ans = float('-inf')
	min_kadane_ans = float('inf')
	max_sum = 0
	min_sum = 0
	total_sum = 0
	check_positive = False
	max_value = float('-inf')
	for i in arr:
		if i > max_value:
			max_value = i
		if i > 0:
			check_positive = True
			break
	if not check_positive:
		return max_value
	for i in arr:
		total_sum = total_sum + i
		max_sum = max_sum + i
		kadane_ans = max(max_sum, kadane_ans)
		if max_sum < 0:
			max_sum = 0
		min_sum = min_sum + i
		min_kadane_ans = min(min_kadane_ans, min_sum)
		if min_sum > 0:
			min_sum = 0
	return max(kadane_ans, total_sum - min_kadane_ans)


def circularSubarraySum(arr, n):
	(max_end, max_so_far, min_end, min_so_far, total_sum) = (arr[0], arr[0], arr[0], arr[0], arr[0])
	for i in range(1, n):
		total_sum += arr[i]
		max_end = max(max_end + arr[i], arr[i])
		max_so_far = max(max_so_far, max_end)
	if max_so_far < 0:
		return max_so_far
	for i in range(1, n):
		min_end = min(min_end + arr[i], arr[i])
		min_so_far = min(min_so_far, min_end)
	p = max(max_so_far, total_sum - min_so_far)
	return p


def circularSubarraySum(arr, n):
	e = 1
	for i in range(n):
		if arr[i] > 0:
			e = 0
	if e == 1:
		return max(arr)
	N = n
	ans = -99999999
	a = 0
	for i in range(N):
		a = a + arr[i]
		if a > ans:
			ans = a
		if a < 0:
			a = 0
	z = ans
	ans = -99999999
	a = 0
	sam = sum(arr)
	for i in range(N):
		arr[i] = arr[i] * -1
	for i in range(N):
		a = a + arr[i]
		if a > ans:
			ans = a
		if a < 0:
			a = 0
	r = sam + ans
	return max(r, z)


def kadane(arr, n):
	max_so_far = 0
	max_ending_here = 0
	for i in range(0, n):
		max_ending_here = max_ending_here + arr[i]
		if max_ending_here < 0:
			max_ending_here = 0
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
	return max_so_far

def circularSubarraySum(arr, n):
	count = 0
	maxx = -sys.maxsize - 1
	for i in range(0, n):
		if arr[i] > maxx:
			maxx = arr[i]
		if arr[i] < 0:
			count = count + 1
	if count == n:
		return maxx
	max_kadane = kadane(arr, n)
	max_wrap = 0
	for i in range(0, n):
		max_wrap += arr[i]
		arr[i] = -arr[i]
	max_wrap = max_wrap + kadane(arr, n)
	if max_wrap > max_kadane:
		return max_wrap
	else:
		return max_kadane


def normalsum(arr, n):
	res = 0
	maxending = 0
	for i in range(n):
		maxending = maxending + arr[i]
		if maxending < 0:
			maxending = 0
		res = max(maxending, res)
	return res

def circularSubarraySum(arr, n):
	count = 0
	maxx = -sys.maxsize - 1
	for i in range(0, n):
		if arr[i] > maxx:
			maxx = arr[i]
		if arr[i] < 0:
			count += 1
	if count == n:
		return maxx
	max_normal = normalsum(arr, n)
	total = 0
	for i in range(n):
		total += arr[i]
		arr[i] = -arr[i]
	max_circular = total + normalsum(arr, n)
	return max(max_normal, max_circular)


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	(mini, maxi, curr_min, curr_max) = (arr[0], arr[0], arr[0], arr[0])
	sm = sum(arr)
	for i in range(1, n):
		curr_max = max(curr_max + arr[i], arr[i])
		maxi = max(maxi, curr_max)
		curr_min = min(curr_min + arr[i], arr[i])
		mini = min(mini, curr_min)
	if mini == sm:
		return maxi
	return max(maxi, sm - mini)


import math

def circularSubarraySum(arr, n):
	max_sum = arr[0]
	cur_sum = arr[0]
	total_sum = arr[0]
	for i in range(1, n):
		total_sum += arr[i]
		cur_sum = max(arr[i], cur_sum + arr[i])
		max_sum = max(max_sum, cur_sum)
	min_sum = arr[0]
	cur_sum = arr[0]
	for i in range(1, n):
		cur_sum = min(arr[i], cur_sum + arr[i])
		min_sum = min(min_sum, cur_sum)
	circular_sum = total_sum - min_sum
	if circular_sum == 0:
		return max_sum
	return max(max_sum, circular_sum)


def circularSubarraySum(arr, n):
	(total, maxSum, curMax, minSum, curMin) = (0, arr[0], 0, arr[0], 0)
	for a in arr:
		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


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	sum = 0
	for i in range(n):
		sum += arr[i]
	curr_max = arr[0]
	max_so_far = arr[0]
	curr_min = arr[0]
	min_so_far = arr[0]
	for i in range(1, n):
		curr_max = max(curr_max + arr[i], arr[i])
		max_so_far = max(max_so_far, curr_max)
		curr_min = min(curr_min + arr[i], arr[i])
		min_so_far = min(min_so_far, curr_min)
	if min_so_far == sum:
		return max_so_far
	return max(max_so_far, sum - min_so_far)


def circularSubarraySum(arr, n):
	(globalMax, globalMin) = (arr[0], arr[0])
	(curMax, curMin) = (0, 0)
	total = 0
	for n in arr:
		curMax = max(curMax + n, n)
		curMin = min(curMin + n, n)
		total += n
		globalMax = max(globalMax, curMax)
		globalMin = min(globalMin, curMin)
	return max(total - globalMin, globalMax) if globalMax > 0 else globalMax


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

def circularSubarraySum(arr, n):
	maxNormal = normalSum(arr)
	if maxNormal < 0:
		return maxNormal
	arraySum = sum(arr)
	for i in range(n):
		arr[i] = -arr[i]
	maxCircular = arraySum + normalSum(arr)
	return max(maxNormal, maxCircular)


def circularSubarraySum(a, n):
	mini = 0
	ans = 0
	sum = 0
	maxi = 0
	an = 0
	for i in range(n):
		mini = min(a[i] + mini, 0)
		if mini < ans:
			ans = mini
		sum = sum + a[i]
	for i in range(n):
		maxi = max(a[i] + maxi, 0)
		if maxi > an:
			an = maxi
	if max(a) < 0:
		return max(a)
	return max(sum - ans, an)


def circularSubarraySum(arr, n):
	curr_max = arr[0]
	curr_min = arr[0]
	so_max = arr[0]
	so_min = arr[0]
	for i in range(1, n):
		curr_max = max(curr_max + arr[i], arr[i])
		so_max = max(curr_max, so_max)
		curr_min = min(curr_min + arr[i], arr[i])
		so_min = min(curr_min, so_min)
	if sum(arr) == so_min:
		return so_max
	else:
		return max(so_max, sum(arr) - so_min)


def circularSubarraySum(arr, n):
	(gmax, gmin) = (arr[0], arr[0])
	(cmax, cmin) = (0, 0)
	tsum = 0
	for i in arr:
		tsum += i
		cmax = max(cmax + i, i)
		cmin = min(cmin + i, i)
		gmax = max(gmax, cmax)
		gmin = min(gmin, cmin)
	if gmax >= 0:
		return max(gmax, tsum - gmin)
	return gmax


def circularSubarraySum(arr, n):
	minsum = normalminSum(arr, n)
	maxsum = normalSub(arr, n)
	arr_sum = 0
	for i in range(n):
		arr_sum += arr[i]
	cirsum = arr_sum - minsum
	if maxsum > 0:
		return max(maxsum, cirsum)
	return maxsum

def normalSub(arr, n):
	res = arr[0]
	maxsum = arr[0]
	for i in range(1, n):
		maxsum = max(maxsum + arr[i], arr[i])
		res = max(res, maxsum)
	return res

def normalminSum(arr, n):
	res = arr[0]
	maxsum = arr[0]
	for i in range(1, n):
		maxsum = min(maxsum + arr[i], arr[i])
		res = min(res, maxsum)
	return res


def circularSubarraySum(arr, n):
	curmax = arr[0]
	maxsofar = arr[0]
	curmin = arr[0]
	minsofar = arr[0]
	s = sum(arr)
	for i in range(1, n):
		curmax = max(curmax + arr[i], arr[i])
		maxsofar = max(maxsofar, curmax)
		curmin = min(curmin + arr[i], arr[i])
		minsofar = min(minsofar, curmin)
	if minsofar == s:
		return maxsofar
	return max(maxsofar, s - minsofar)


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	total = sum(arr)
	currMax = arr[0]
	currMin = arr[0]
	max_sofar = arr[0]
	min_sofar = arr[0]
	for i in range(1, n):
		currMax = max(currMax + arr[i], arr[i])
		max_sofar = max(max_sofar, currMax)
		currMin = min(currMin + arr[i], arr[i])
		min_sofar = min(currMin, min_sofar)
	if max_sofar < 0:
		return max_sofar
	return max(max_sofar, total - min_sofar)


def circularSubarraySum(arr, n):
	max_sum = float('-inf')
	min_sum = float('inf')
	curr_max = 0
	curr_min = 0
	total_sum = 0
	for i in range(n):
		curr_max = max(curr_max + arr[i], arr[i])
		max_sum = max(max_sum, curr_max)
		curr_min = min(curr_min + arr[i], arr[i])
		min_sum = min(min_sum, curr_min)
		total_sum += arr[i]
	if max_sum > 0:
		return max(max_sum, total_sum - min_sum)
	else:
		return max_sum


def maxSubArr(l, n):
	maxEnding = [0] * n
	maxEnding[0] = l[0]
	for i in range(1, n):
		maxEnding[i] = max(l[i], l[i] + maxEnding[i - 1])
	return max(maxEnding)

def minSubArr(l, n):
	totalSum = sum(l)
	minEnding = [0] * n
	minEnding[0] = l[0]
	for i in range(1, n):
		minEnding[i] = min(l[i], l[i] + minEnding[i - 1])
	res = min(minEnding)
	if totalSum - res == 0:
		return float('-inf')
	else:
		return totalSum - res

def circularSubarraySum(l, n):
	if n == 1:
		return l[0]
	ans = max(maxSubArr(l, n), minSubArr(l, n))
	return ans


import math

def circularSubarraySum(arr, n):
	normal = maxNormal(arr, n)
	if normal < 0:
		return normal
	circular = maxCircular(arr, n)
	return max(normal, circular)

def maxNormal(arr, n):
	cursum = arr[0]
	res = cursum
	for i in range(1, n):
		cursum = max(cursum + arr[i], arr[i])
		res = max(res, cursum)
	return res

def maxCircular(arr, n):
	totsum = arr[0]
	cursum = arr[0]
	res = cursum
	for i in range(1, n):
		totsum += arr[i]
		cursum = min(cursum + arr[i], arr[i])
		res = min(res, cursum)
	return totsum - res
	return res


import math

def max_sub(arr):
	curr_sum = 0
	max_sum = -math.inf
	for i in arr:
		curr_sum += i
		if max_sum < curr_sum:
			max_sum = curr_sum
		if curr_sum < 0:
			curr_sum = 0
	return max_sum

def one(arr, n):
	total = 0
	for i in range(n):
		total += arr[i]
		arr[i] = -arr[i]
	curr_sum = 0
	max_sum = -math.inf
	for i in arr:
		curr_sum += i
		if max_sum < curr_sum:
			max_sum = curr_sum
		if curr_sum < 0:
			curr_sum = 0
	return total + max_sum

def circularSubarraySum(arr, n):
	val1 = max_sub(arr)
	if val1 < 0:
		return val1
	val2 = one(arr, n)
	return max(val1, val2)


import sys

def kadanesalgo(arr, n):
	currSum = arr[0]
	maxSum = arr[0]
	for i in range(1, n):
		currSum = max(currSum + arr[i], arr[i])
		maxSum = max(maxSum, currSum)
	return maxSum

def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	sum1 = kadanesalgo(arr, n)
	if sum1 < 0:
		return sum1
	totalSum = sum(arr)
	arr = [-item for item in arr]
	sum2 = kadanesalgo(arr, n)
	return max(totalSum + sum2, sum1)


def circularSubarraySum(arr, n):
	normal_max_sub_array_sum = max_sub_array_sum(arr, n)
	if normal_max_sub_array_sum < 0:
		return normal_max_sub_array_sum
	array_sum = sum(arr)
	arr = [-item for item in arr]
	inverted_max_sub_array_sum = max_sub_array_sum(arr, n)
	return max(normal_max_sub_array_sum, array_sum + inverted_max_sub_array_sum)

def max_sub_array_sum(arr, n):
	res = maxEnding = arr[0]
	for item in arr[1:]:
		maxEnding = max(maxEnding + item, item)
		res = max(res, maxEnding)
	return res


def circularSubarraySum(arr, n):
	s = 0
	all_neg = 1
	for a in arr:
		s += a
		if a > 0:
			all_neg = 0
	if all_neg:
		return max(arr)
	ans = -1000001
	curr = 0
	for a in arr:
		if curr + a >= 0:
			curr += a
		else:
			curr = 0
		ans = max(ans, curr)
	total = 0
	curr = 0
	for a in arr:
		if curr + a <= 0:
			curr += a
		else:
			curr = 0
		total = min(total, curr)
	ans = max(ans, s - total)
	return ans


def ns(a, n):
	ans = 0
	s = 0
	for i in a:
		x = s + i
		if x > 0:
			s = x
		else:
			s = 0
		ans = max(ans, s)
	return ans

def circularSubarraySum(a, n):
	NS = ns(a, n)
	s = sum(a)
	if NS == 0:
		return max(a)
	for i in range(n):
		a[i] = -a[i]
	return max(NS, s + ns(a, n))


def circularSubarraySum(arr, n):
	minending = arr[0]
	res1 = arr[0]
	sum = 0
	for i in range(1, n):
		minending = min(minending + arr[i], arr[i])
		res1 = min(res1, minending)
	for i in range(n):
		sum += arr[i]
	overall_res1 = sum - res1
	maxending = arr[0]
	res2 = arr[0]
	for i in range(1, n):
		maxending = max(maxending + arr[i], arr[i])
		res2 = max(res2, maxending)
	res = max(overall_res1, res2)
	if res == 0:
		maxi = arr[0]
		for i in range(1, n):
			if arr[i] > maxi:
				maxi = arr[i]
		res = maxi
	return res


def KadanesAlgo(arr, n):
	for i in range(1, n):
		arr[i] = max(arr[i - 1] + arr[i], arr[i])
	return max(arr)

def circularSubarraySum(arr, n):
	normalMax = KadanesAlgo(arr.copy(), n)
	if normalMax < 0:
		return normalMax
	total_sum = sum(arr)
	for i in range(n):
		arr[i] *= -1
	circularMax = KadanesAlgo(arr, n)
	return max(normalMax, total_sum + circularMax)


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	z = 0
	for i in range(n):
		if arr[i] < 0:
			z = z + 1
	if z == n:
		return max(arr)

	def kdan(arr, n):
		sm = 0
		ind = -1
		mx = 0
		for i in range(n):
			sm = sm + arr[i]
			if sm <= 0:
				sm = 0
				ind = i + 1
			if mx < sm:
				mx = sm
		return mx
	mx1 = kdan(arr, n)
	totalsm = 0
	for i in range(n):
		totalsm += arr[i]
		arr[i] = 0 - arr[i]
	sm1 = kdan(arr, n)
	mx2 = totalsm - -sm1
	return max(mx1, mx2)


def circularSubarraySum(arr, n):
	total = sum(arr)
	maxi = arr[0]
	mini = arr[0]
	maxi_sum = 0
	min_sum = 0
	for i in range(n):
		maxi_sum += arr[i]
		if maxi_sum > maxi:
			maxi = maxi_sum
		if maxi_sum < 0:
			maxi_sum = 0
		min_sum += arr[i]
		if min_sum < mini:
			mini = min_sum
		if min_sum > 0:
			min_sum = 0
	if mini == total:
		return maxi
	else:
		return max(maxi, total - mini)


def circularSubarraySum(a, n):
	mini = 10 ** 9
	s = 0
	currmin = 0
	maxi = -10 ** 9
	currmax = 0
	for i in range(n):
		currmin += a[i]
		currmax += a[i]
		maxi = max(maxi, currmax)
		mini = min(mini, currmin)
		if currmin > 0:
			currmin = 0
		if currmax < 0:
			currmax = 0
		s += a[i]
	if maxi > 0:
		return max(maxi, s - mini)
	return maxi


def kadane(arr):
	max_so_far = arr[0]
	max_ending_here = arr[0]
	for i in range(1, len(arr)):
		max_ending_here = max(arr[i], max_ending_here + arr[i])
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far

def circularSubarraySum(arr, n):
	max_sum_non_circular = kadane(arr)
	min_sum_non_circular = kadane([-num for num in arr])
	total_sum = sum(arr)
	max_sum_circular = total_sum + min_sum_non_circular
	if max_sum_circular == 0:
		return max_sum_non_circular
	return max(max_sum_circular, max_sum_non_circular)


def kadane_min(arr, n):
	import sys
	mn = sys.maxsize
	mn_here = mn
	for i in range(n):
		if mn_here > 0:
			mn_here = arr[i]
		else:
			mn_here += arr[i]
		mn = min(mn, mn_here)
	return mn

def circularSubarraySum(arr, n):
	sm = sum(arr)
	if n == 1:
		return arr[0]
	curr_min = curr_max = gmax = gmin = arr[0]
	for i in range(1, n):
		curr_min = min(curr_min + arr[i], arr[i])
		curr_max = max(curr_max + arr[i], arr[i])
		gmax = max(gmax, curr_max)
		gmin = min(gmin, curr_min)
	if gmin == sm:
		return gmax
	return max(gmax, sm - gmin)


def circularSubarraySum(arr, n):
	if len(arr) == 1:
		return arr[0]
	if len(arr) == 0:
		return 0
	circle = 0
	ans = 0
	maxsum = maxsumm(arr, n)
	minsum = minsumm(arr, n)
	if maxsum < 0:
		return maxsum
	sum = 0
	for i in arr:
		sum += i
	circle = sum - minsum
	ans = max(circle, maxsum)
	return ans

def maxsumm(arr, n):
	maxsum = arr[0]
	maxending = arr[0]
	for i in range(1, len(arr)):
		maxending = max(maxending + arr[i], arr[i])
		maxsum = max(maxsum, maxending)
	return maxsum

def minsumm(arr, n):
	minsum = arr[0]
	maxending = arr[0]
	for i in range(1, len(arr)):
		maxending = min(maxending + arr[i], arr[i])
		minsum = min(minsum, maxending)
	return minsum


def circularSubarraySum(arr, n):
	ma = maxi(arr, n)
	if ma < 0:
		return ma
	temp = []
	for i in arr:
		temp.append(-i)
	mi = maxi(temp, n)
	su = sum(arr)
	return max(ma, su + mi)

def maxi(arr, n):
	cur = arr[0]
	ma = arr[0]
	for i in range(1, n):
		cur = max(cur + arr[i], arr[i])
		ma = max(ma, cur)
	return ma


def circularSubarraySum(arr, n):
	cs = mxs = mns = mx = mn = arr[0]
	for i in range(1, n):
		mx = max(arr[i], mx + arr[i])
		mxs = max(mxs, mx)
		mn = min(arr[i], mn + arr[i])
		mns = min(mns, mn)
		cs += arr[i]
	if mxs > 0:
		return max(mxs, cs - mns)
	else:
		return mxs


def circularSubarraySum(arr, n):
	x = kadana(arr)
	y = 0
	for i in range(n):
		y += arr[i]
		arr[i] *= -1
	z = kadana(arr)
	if y + z == 0:
		return x
	return max(x, y + z)

def kadana(arr):
	sum = 0
	res = float('-inf')
	for ele in arr:
		sum += ele
		res = max(sum, res)
		if sum < 0:
			sum = 0
	return res


def kadane(arr, N):
	max_so_far = -99
	max_end = 0
	for i in range(0, len(arr)):
		max_end += arr[i]
		if max_end > max_so_far:
			max_so_far = max_end
		if max_end < 0:
			max_end = 0
	return max_so_far

def circularSubarraySum(arr, n):
	n_kadane_number = kadane(arr, n)
	if n_kadane_number < 0:
		return n_kadane_number
	sum = 0
	for i in range(0, len(arr)):
		sum += arr[i]
		arr[i] = -arr[i]
	kadane_number = kadane(arr, n)
	return max(sum + kadane_number, n_kadane_number)


def circularSubarraySum(arr, n):
	ns = maxNormal(arr, n)
	if ns < 0:
		return ns
	cs = maxCircular(arr, n)
	return max(ns, cs)

def maxNormal(arr, n):
	curr = arr[0]
	max_sub = arr[0]
	for x in arr[1:]:
		max_sub = max(x, max_sub + x)
		curr = max(curr, max_sub)
	return curr

def maxCircular(arr, n):
	arr_neg = [-x for x in arr]
	nm = maxNormal(arr_neg, n)
	return sum(arr) + nm


def max_normal_subarray(arr):
	res = arr[0]
	curr_sum = 0
	for i in range(len(arr)):
		curr_sum = max(curr_sum + arr[i], arr[i])
		res = max(res, curr_sum)
	return res

def min_normal_subarray(arr):
	res = arr[0]
	curr_sum = 0
	for i in range(len(arr)):
		curr_sum = min(curr_sum + arr[i], arr[i])
		res = min(res, curr_sum)
	return res

def circularSubarraySum(arr, n):
	x = max_normal_subarray(arr)
	if x >= 0:
		temp = [-item for item in arr]
		y2 = sum(arr) + max_normal_subarray(temp)
		return max(x, y2)
	return x


def max_normal_subarray(arr):
	res = arr[0]
	curr_sum = 0
	for i in range(len(arr)):
		curr_sum = max(curr_sum + arr[i], arr[i])
		res = max(res, curr_sum)
	return res

def min_normal_subarray(arr):
	res = arr[0]
	curr_sum = 0
	for i in range(len(arr)):
		curr_sum = min(curr_sum + arr[i], arr[i])
		res = min(res, curr_sum)
	return res

def circularSubarraySum(arr, n):
	x = max_normal_subarray(arr)
	if x >= 0:
		y1 = sum(arr) - min_normal_subarray(arr)
		return max(x, y1)
	return x


def circularSubarraySum(arr, n):
	max_sum = -float('inf')
	curr_sum = 0
	for i in range(n):
		curr_sum = max(arr[i], curr_sum + arr[i])
		max_sum = max(max_sum, curr_sum)
	if max_sum < 0:
		return max(arr)
	min_sum = float('inf')
	curr_sum = 0
	for i in range(n):
		curr_sum = min(arr[i], curr_sum + arr[i])
		min_sum = min(min_sum, curr_sum)
	total_sum = sum(arr)
	max_circular_sum = max(total_sum - min_sum, max_sum)
	return max_circular_sum


def circularSubarraySum(arr, n):
	ans = max(arr)
	min_tot = 0
	neg = 0
	tot = 0
	cur_max = 0
	for i in range(n):
		if min_tot > 0:
			min_tot = arr[i]
		else:
			min_tot += arr[i]
		neg = min(neg, min_tot)
		tot += arr[i]
		if cur_max <= 0:
			cur_max = arr[i]
		else:
			cur_max += arr[i]
		ans = max(cur_max, ans)
	ans = max(ans, tot - neg)
	if ans == 0:
		return max(arr)
	else:
		return ans


def subArraySum(arr, n):
	(mx_sum, ending_sum) = (arr[0], arr[0])
	for i in range(1, n):
		ending_sum = max(ending_sum + arr[i], arr[i])
		mx_sum = max(mx_sum, ending_sum)
	return mx_sum

def circularSubarraySum(arr, n):
	mx_sum = subArraySum(arr, n)
	if mx_sum <= 0:
		return mx_sum
	arr_sum = 0
	for i in range(n):
		arr_sum += arr[i]
		arr[i] = -arr[i]
	circular_sum = arr_sum + subArraySum(arr, n)
	return max(circular_sum, mx_sum)


def circularSubarraySum(arr, n):
	maxi = max(arr)
	if maxi <= 0:
		return maxi
	cursum = arr[0]
	maxisum = arr[0]
	minsum = arr[0]
	curmin = arr[0]
	for i in arr[1:]:
		cursum = max(cursum + i, i)
		maxisum = max(maxisum, cursum)
		curmin = min(curmin + i, i)
		minsum = min(curmin, minsum)
	res = max(maxisum, sum(arr) - minsum)
	return res


def circularSubarraySum(arr, n):
	max_so_far = arr[0]
	max_ending_here = arr[0]
	min_so_far = arr[0]
	min_ending_here = arr[0]
	total_sum = arr[0]
	for i in range(1, n):
		max_ending_here = max(arr[i], max_ending_here + arr[i])
		max_so_far = max(max_so_far, max_ending_here)
		min_ending_here = min(arr[i], min_ending_here + arr[i])
		min_so_far = min(min_so_far, min_ending_here)
		total_sum += arr[i]
	if max_so_far < 0:
		return max_so_far
	max_circular_sum = total_sum - min_so_far
	return max(max_so_far, max_circular_sum)


def circularSubarraySum(arr, n):
	(sum_for_min, sum_for_max, maxx, minn) = (arr[0], arr[0], arr[0], arr[0])
	for i in range(1, n):
		if sum_for_max < 0:
			sum_for_max = arr[i]
		else:
			sum_for_max += arr[i]
		if sum_for_min > 0:
			sum_for_min = arr[i]
		else:
			sum_for_min += arr[i]
		maxx = max(maxx, sum_for_max)
		minn = min(minn, sum_for_min)
	sum_of_arr = sum(arr)
	if minn == sum_of_arr:
		return maxx
	return max(maxx, sum_of_arr - minn)


def circularSubarraySum(arr, n):
	s = 0
	for i in arr:
		s += i
	curr = 0
	mn = 0
	for i in arr:
		if i <= 0:
			curr += i
			mn = min(mn, curr)
		else:
			curr = min(curr + i, 0)
	curr = max(arr[0], 0)
	mx = arr[0]
	for i in arr[1:]:
		if i >= 0:
			curr += i
			mx = max(mx, curr)
		elif i > mx:
			mx = i
		else:
			curr = max(0, curr + i)
	if mx < 0:
		return mx
	return max(mx, s - mn)


def circularSubarraySum(arr, n):
	(mp, mn) = (arr[0], arr[0])
	(cp, cn) = (arr[0], arr[0])
	s = arr[0]
	for i in range(1, n):
		s += arr[i]
		cp = max(arr[i], arr[i] + cp)
		cn = min(arr[i], cn + arr[i])
		(mp, mn) = (max(mp, cp), min(mn, cn))
	if s != mn:
		mp = max(mp, s - mn)
	return mp


def circularSubarraySum(arr, n):
	su = arr[0]
	curr = arr[0]
	final1 = arr[0]
	for i in range(1, len(arr)):
		su = su + arr[i]
		curr = max(curr + arr[i], arr[i])
		if curr > final1:
			final1 = curr
	curr = arr[0]
	final2 = arr[0]
	for i in range(1, len(arr)):
		curr = min(curr + arr[i], arr[i])
		if curr < final2:
			final2 = curr
	if su != final2:
		return max(su - final2, final1)
	else:
		return max(final2, final1)


def circularSubarraySum(a, n):
	if len(a) == 1:
		return a[0]

	def maxSubArraySum(a, n):
		max_so_far = float('-inf')
		max_ending_here = 0
		for i in range(0, n):
			max_ending_here = max_ending_here + a[i]
			if max_so_far < max_ending_here:
				max_so_far = max_ending_here
			if max_ending_here < 0:
				max_ending_here = 0
		return max_so_far

	def minSubArraySum(a, n):
		min_so_far = float('+inf')
		min_ending_here = 0
		for i in range(0, n):
			min_ending_here = min_ending_here + a[i]
			if min_so_far > min_ending_here:
				min_so_far = min_ending_here
			if min_ending_here > 0:
				min_ending_here = 0
		return min_so_far
	if minSubArraySum(a, n) == sum(a):
		return maxSubArraySum(a, n)
	else:
		mcss = max(maxSubArraySum(a, n), sum(a) - minSubArraySum(a, n))
		return mcss


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	sum = 0
	for i in range(n):
		sum += arr[i]
	cur_max = arr[0]
	cur_min = arr[0]
	maxi = arr[0]
	mini = arr[0]
	for i in range(1, n):
		cur_max = max(cur_max + arr[i], arr[i])
		cur_min = min(cur_min + arr[i], arr[i])
		maxi = max(maxi, cur_max)
		mini = min(mini, cur_min)
	if mini == sum:
		return maxi
	return max(maxi, sum - mini)


def kadanesalgo(arr):
	res = arr[0]
	maximum_so_far = arr[0]
	for curr_ele in range(1, len(arr)):
		maximum_so_far = max(maximum_so_far + arr[curr_ele], arr[curr_ele])
		res = max(maximum_so_far, res)
	return res

def circularSubarraySum(arr, n):
	kadanes = kadanesalgo(arr)
	if kadanes < 1:
		return kadanes
	arr_sum = 0
	for i in range(len(arr)):
		arr_sum += arr[i]
		arr[i] = -arr[i]
	maxcircularsum = kadanesalgo(arr) + arr_sum
	return max(kadanes, maxcircularsum)


def circularSubarraySum(arr, n):
	arrsum = 0
	resmax = arr[0]
	countmax = arr[0]
	resmin = arr[0]
	countmin = arr[0]
	for i in range(n):
		arrsum += arr[i]
	for i in range(1, n):
		countmax = max(countmax + arr[i], arr[i])
		resmax = max(countmax, resmax)
		countmin = min(countmin + arr[i], arr[i])
		resmin = min(countmin, resmin)
	if resmin == arrsum:
		return resmax
	return max(resmax, arrsum - resmin)


def circularSubarraySum(arr, n):
	res1 = get_normal(arr, n)
	if res1 < 0:
		return res1
	arr_sum = 0
	for i in range(0, n):
		arr_sum += arr[i]
		arr[i] = -arr[i]
	return max(arr_sum + get_normal(arr, n), res1)

def get_normal(arr, n):
	max_so_far = -999999
	max_ele = 0
	for i in range(n):
		max_ele = max_ele + arr[i]
		if max_so_far < max_ele:
			max_so_far = max_ele
		if max_ele < 0:
			max_ele = 0
	return max_so_far
	print(res)


def circularSubarraySum(arr, n):
	max_sum = arr[0]
	curr_sum = arr[0]
	for i in range(1, n):
		curr_sum = max(arr[i], curr_sum + arr[i])
		max_sum = max(max_sum, curr_sum)
	min_sum = arr[0]
	curr_sum = arr[0]
	for i in range(1, n):
		curr_sum = min(arr[i], curr_sum + arr[i])
		min_sum = min(min_sum, curr_sum)
	total_sum = sum(arr)
	if total_sum == min_sum:
		return max_sum
	else:
		return max(max_sum, total_sum - min_sum)


def circularSubarraySum(arr, n):
	nums = arr
	if max(nums) < 0:
		return max(nums)

	def fun(nums):
		ans = nums[0]
		cs = nums[0]
		for i in range(1, len(nums)):
			cs = max(nums[i], cs + nums[i])
			ans = max(cs, ans)
		return ans
	maxsum = fun(nums)
	totalsum = sum(nums)
	for i in range(len(nums)):
		nums[i] = -nums[i]
	minsum = fun(nums)
	return max(maxsum, minsum + totalsum)


def circularSubarraySum(a, n):
	if len(a) == 1:
		return a[0]
	max_sum = a[0]
	max_so_far = a[0]
	min_sum = a[0]
	min_so_far = a[0]
	tot_sum = sum(a)
	for i in range(1, len(a)):
		max_so_far = max(max_so_far + a[i], a[i])
		max_sum = max(max_sum, max_so_far)
		min_so_far = min(min_so_far + a[i], a[i])
		min_sum = min(min_sum, min_so_far)
	if min_so_far == tot_sum:
		return max_sum
	return max(max_sum, tot_sum - min_sum)


def circularSubarraySum(arr, n):
	if n == 1:
		return arr[0]
	else:
		tsum = sum(arr)
		res = arr[0]
		maxend = arr[0]
		res2 = arr[0]
		minend = arr[0]
		for i in range(1, n):
			maxend = max(maxend + arr[i], arr[i])
			res = max(res, maxend)
			minend = min(minend + arr[i], arr[i])
			res2 = min(res2, minend)
		if res2 == tsum:
			return res
		else:
			return max(res, tsum - res2)