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: interview

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]
        # print(right_max)
        
        left_max = A[0]
        left_sum = A[0]
        for i in range(1, len(A)-1):
            # print(A[i], left_max, left_sum)
            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) # 2
            curMax = max(curMax + num, num) # 7
            maxi = max(maxi, curMax) # 7
            mini = min(mini, curMin) # -3
            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:
        # case 1, kadane's algo
        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)
        
        # case 2, wrapping
        
        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:
        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)
        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:
        
        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)

        
        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:
        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]) # i's, increasing by P[i]
        for j in range(1, len(dp)):
            # If the smallest i is too small, remove it.
            if deque[0] < j-len(A):
                deque.popleft()

            # The optimal i is deque[0], for cand. answer P[j] - P[i].
            res = max(res, dp[j] - dp[deque[0]])

            # Remove any i1's with P[i2] <= P[i1].
            while deque and dp[j] <= dp[deque[-1]]:
                deque.pop()

            deque.append(j)
        return res
        '''
        As before, sum(nums[i:i+k]) = dp[i+k]-dp[i]
        now, sum[i+k:i] = dp[len(A)-(i+k)]+dp[i]
        '''
        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') # maximum non-empty subarray sum
            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 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, 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, 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
            


# case1: ---------|
    
# case2: ---------|----------
#             |--------|
#              suf  pre
#        maxsubarray = total - min(subarray)


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:
        # Maximum Sum Circular Subarray
        # 8/22/20 3:41
        total, maxSum = 0, A[0]
        curMax, minSum, curMin = 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 total != minSum else maxSum
    
    

# input: [5,-3,5]
# Output:7
# Expected:10

                    
                
            
            
         


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:
        curmax, curmin = 0 , 0
        total = 0
        maxsum = minsum = A[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)
            #print(end, stack, 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:
        #naive will be n^2: try every possible start position
        
        #3 cases
        
        minSum = A[0]
        maxSum = A[0]
        maximum = A[0]
        minimum = A[0]
        for i in range(1, len(A)):
            if A[i] > maxSum + A[i]:
                maxSum = A[i]
            else:
                maxSum += A[i]
            maximum = max(maximum, maxSum)
            if A[i] < minSum + A[i]:
                minSum = A[i]
            else:
                minSum += A[i]
            minimum = min(minimum, minSum)
        
        minimum = sum(A) - minimum
        if minimum == 0: #means the entire araay is negative, so we take the max element
            return maximum
        return max(maximum, minimum)
        
        #take the max of 3 cases
        #1. maximum
        #2. total - minimum
        #3. if all negatives, then the max should be the maximum
        
        #[-2,-3,-1]. Take a look at this case, for example. 


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:
        mx = float('-inf')
        curr = 0
        for x in A:
            if curr >= 0:
                curr += x
            else:
                curr = x
            mx = max(mx, curr)
        cumSum = []
        curr = 0
        for x in A:
            curr += x
            cumSum.append(curr)
        revCumSum = []
        curr = 0
        for x in reversed(A):
            curr += x
            revCumSum.append(curr)
        for i in range(1, len(A)):
            revCumSum[i] = max(revCumSum[i-1], revCumSum[i])
        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:
        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)

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)


from sys import maxsize
class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        i=1
        n=len(A)
        # A=A+A
        # end = n
        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_
        
#         left_acc = [0] * n
#         left_acc[0] = A[0]
#         for idx in range(1, n):
#             left_acc[idx] = A[idx] + left_acc[idx - 1]
            
        
#         right_acc = [0] * n
#         right_acc[-1] = A[-1]
#         for idx in range(n - 2, -1, -1):
#             right_acc[idx] = A[idx] + right_acc[idx + 1]
        
#         print(left_acc)
#         print(right_acc)
#         left, right = 0, n - 1
#         while left < right:
#             max_ = max(max_, left_acc[left] + right_acc[right])
#             if left_acc[left] > right_acc[right]:
#                 right -= 1
#             else:
#                 left += 1
        
#         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
                
 
            
        
            

            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
#             currMaxSum = 0
#             currMinSum = 0
#             flag = False
#             maxSum = float('-inf')
#             minSum = float('inf')
#             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 not flag:
#                 return maxSum 

#             else:
#                 return max(maxSum, totalSum-minSum)
            
                    
                
                

            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
#         ans1 = cur = None 
#         for x in A:
#             cur = x + max(cur, 0)
#             ans1 = max(ans1, cur)
            
#         ans2 = cur = float(\"inf\")
#         for i in range(1, len(A)):
#             cur = A[i] + min(cur, 0)
#             ans2 = min(ans2, cur)
#         ans2 = sum(A) - ans2
        
#         ans3 = cur = float(\"inf\")
#         for i in range(len(A)-1):
#             cur = A[i] + min(cur, 0)
#             ans3 = min(ans3, cur)
#         ans3 = sum(A) - ans3
        
#         return max(ans1, ans2, ans3)
        
        
        

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         track = [[0 for j in range(len(A))] for j in range(len(A))]
#         max_val = min(A)
#         for i in range(len(A)):
#             track[i][i] = A[i]
#             for j in range(i+1, len(A)):
#                     track[i][j] = track[i][j-1] + A[j]
#                     max_val = max(max_val, track[i][j])
#             max_val = max(max_val, track[i][i])
                    
#         #print(track)
#         for i in range(len(A)-1, 0, -1):
#             for j in range(0, i):
#                 track[i][j] = track[i][len(track) - 1] + track[0][j]
#                 max_val = max(max_val, track[i][j])
                
#         #print(track)
#         return max_val]


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
            
            currMaxSum = 0
            currMinSum = 0
            flag = False
            maxSum = float('-inf')
            minSum = float('inf')
            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 not flag:
                return maxSum 

            else:
                return max(maxSum, totalSum-minSum)
            
                    
                
                

            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
#         ans1 = cur = None 
#         for x in A:
#             cur = x + max(cur, 0)
#             ans1 = max(ans1, cur)
            
#         ans2 = cur = float(\"inf\")
#         for i in range(1, len(A)):
#             cur = A[i] + min(cur, 0)
#             ans2 = min(ans2, cur)
#         ans2 = sum(A) - ans2
        
#         ans3 = cur = float(\"inf\")
#         for i in range(len(A)-1):
#             cur = A[i] + min(cur, 0)
#             ans3 = min(ans3, cur)
#         ans3 = sum(A) - ans3
        
#         return max(ans1, ans2, ans3)
        
        
        

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         track = [[0 for j in range(len(A))] for j in range(len(A))]
#         max_val = min(A)
#         for i in range(len(A)):
#             track[i][i] = A[i]
#             for j in range(i+1, len(A)):
#                     track[i][j] = track[i][j-1] + A[j]
#                     max_val = max(max_val, track[i][j])
#             max_val = max(max_val, track[i][i])
                    
#         #print(track)
#         for i in range(len(A)-1, 0, -1):
#             for j in range(0, i):
#                 track[i][j] = track[i][len(track) - 1] + track[0][j]
#                 max_val = max(max_val, track[i][j])
                
#         #print(track)
#         return max_val


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
#         total, maxSum, curMax, minSum, curMin = 0, float('-inf'), 0, float('inf'), 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
    
    
        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(the max subarray sum, the total sum - the min subarray sum)
        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) 

# method 1  append array's copy at back of it. then apply kadane's algorithm
# *not work* because we can only attain maximum n size window but here it can be 2n

# method 2  sliding window  max window size = n
# *not work* because there is no way to move back of window

# method 3  modified kadane's algorithm(see in lee215's solution)
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)
        #print(maxSum)
        #print(minSum)
        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:
        # 1. get max subarray sum
        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
        
        # 2. get min subarray sum
        minSum = curSum = A[0]
        for i in range(1, len(A)):
            curSum = min(A[i], A[i] + curSum)
            minSum = min(minSum, curSum)
        
        # 3. compare (max subarray sum) with (total sum - min subarray sum)
        return max(sum(A)-minSum, maxSum)

#Two cases:
#MaxSubarray = normal -> proceed normally
#MaxSubarray = circular -> total sum - minSubarray
#return max(maxSubarray, maxSubarraycircular
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)

#Two cases:
#MaxSubarray = normal -> proceed normally
#MaxSubarray = circular -> total sum - minSubarray
#return max(maxSubarray, maxSubarraycircular
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
        return max(circular_max, global_max) if global_max > 0 else global_max

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_start_index = [0]
        
#         A.extend(A)
#         print(A)
#         for i in range(1, len(A)):
#             prev = max_sub_ending[i-1]
#             if prev <= 0:
#                 max_sub_start_index.append(i)
#                 max_sub_ending.append(A[i])
#             if i - max_sub_start_index[-1] < n:
#                 max_sub_start_index.append(max_sub_start_index[-1])
#                 max_sub_ending.append(A[i]+max_sub_ending[-1])
#             elif (i - max_sub_start_index[-1]) == n:
#                 index_len = len(max_sub_start_index)
#                 val = max_sub_start_index[index_len-n]
#                 current_sum = max_sub_ending[-1] - val
#                 if current_sum <= 0:
#                     max_sub_start_index.append(i)
#                     max_sub_ending.append(A[i])
#                 else:
#                     max_sub_start_index.append(max_sub_start_index[-1]+1)
#                     max_sub_ending.append(A[i]+current_sum)
#         print(max_sub_ending)
#         return max(max_sub_ending)
        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
        
#         cycle = max_sub_ending[-1]
#         if cycle <= 0:
#             return max(max_sub_ending)
        
#         for i in range(max_sub_ending_index[-1]):
#             if cycle <= 0:
#                 return max(max_sub_ending)
            
#             max_sub_ending_index[i] = cycle+A[i]
#             cycle = max_sub_ending_index[i]
#         return max(max_sub_ending)
        
#         total = sum(A)
        
#         #left sum
#         left_sum = [A[0]]
#         left = A[0]
        
#         for i in range(1, len(A)):
            
#             left = left+A[i]
#             left_sum.append(left)
        
#         #right sum
#         right = A[-1]
#         right_sum = [right]
        
#         for i in range(len(A)-2, -1, -1):
            
#             right += A[i]
#             right_sum.append(right)

#         right_sum.reverse()
        
#         max_sub = total

#         for i in range(0, len(A)):
#             for j in range(i, len(A)):
#                 left, right = 0, 0
#                 if i != 0:
#                     left = left_sum[i-1]
#                 if j != (len(A) -1):
#                     right = right_sum[j+1]
#                 max_sub = max(max_sub, total - left - right , left+right)
        
#         #corner case
#         if max(A) < 0:
#             return max(A)
#         return max_sub


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        #On
        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]
        #get maxsum and minsum
        # total-minsum and maxsum
        if total==minsum:
            return maxsum
        else:
            return max(maxsum,total-minsum)
            
        
        
        
        
        
        
        
#         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]
#         # get second case now
#         #print(optsum)
#         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:
        #N2 solution
#         n = len(A)
#         maxSum = -float('inf')

#         for i in range(n):
#             currSum = 0
#             for j in range(n):
#                 ind = (i+j)%n
#                 ele = A[ind]
                
#                 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

#         return maxSum
    
        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

'''
53. Maximum Subarray 无循环
    dp[i] = max(A[i], dp[i-1] + A[i])
    显然当dp[i-1] < 0 时， dp[i] = A[i]，则有：
    dp[i] = A[i] + max(dp[i-1], 0)

类比53，此题加了循环。也就是找到尾部和开头的最大正数组。

https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass

但其实就是找到中间的最负子数组。
'''


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


# r = Solution()
# a = r.maxSubarraySumCircular([3,-1,2,-1])
# print(a)


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        #On
        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]
        # get second case now
        #print(optsum)
        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[i] = max_{j >= i} rightsums[j]
        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
    
    
#         total = sum(A)
#         max_sum_ending_i = [A[0]]
#         prev = max_sum_ending_i[-1]
        
        
#         for i in range(1, len(A)):
#             if prev <= 0:
#                 max_sum_ending_i.append(A[i])
#             else:
#                 max_sum_ending_i.append(max_sum_ending_i[-1]+A[i])
#             prev = max_sum_ending_i[-1]
        
#         min_sum_ending_i = [A[0]]
#         prev = min_sum_ending_i[-1]

#         for i in range(1, len(A)):
#             if prev >= 0:
#                 min_sum_ending_i.append(A[i])
#             else:
#                 min_sum_ending_i.append(min_sum_ending_i[-1]+A[i])
#             prev = min_sum_ending_i[-1]
        
#         if max(A) > 0:
#             return max(total - min(min_sum_ending_i), max(max_sum_ending_i))
#         else:
#             return max(A)


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(object):
#     def maxSubarraySumCircular(self, A):
#         N = len(A)

#         ans = float('-inf')
#         cur = 0
#         for x in A:
#             cur = x + max(cur, 0)
#             ans = max(ans, cur)

#         # ans is the answer for 1-interval subarrays.
#         # Now, let's consider all 2-interval subarrays.
#         # For each i, we want to know
#         # the maximum of sum(A[j:]) with j >= i+2

#         # rightsums[i] = sum(A[i:])
#         rightsums = [None] * N
#         rightsums[-1] = A[-1]
#         for i in xrange(N-2, -1, -1):
#             rightsums[i] = rightsums[i+1] + A[i]

#         # maxright[i] = max_{j >= i} rightsums[j]
#         maxright = [None] * N
#         maxright[-1] = rightsums[-1]
#         for i in xrange(N-2, -1, -1):
#             maxright[i] = max(maxright[i+1], rightsums[i])

#         leftsum = 0
#         for i in xrange(N-2):
#             leftsum += A[i]
#             ans = max(ans, leftsum + maxright[i+2])
#         return ans
    
class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        
        N = len(A)
        ans = float('-inf')
        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+2])
        
        return ans


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:
        ans1 = cur = 0
        for x in A:
            cur = x + max(cur, 0)
            ans1 = max(ans1, cur)
        
        ans2 = cur = 0
        for i in range(1, len(A)):
            cur = A[i] + min(cur, 0)
            ans2 = min(ans2, cur)
        ans2 = sum(A) - ans2
        
        ans3 = cur = 0
        for i in range(len(A)-1):
            cur = A[i] + 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, 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=-1e10
        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)
        
        
        # n = len(A)
        # A *= 2
        # ans = [A[0]] + [0] * (len(A) - 1)
        # q = collections.deque([(0, A[0])])
        # cur = A[0]
        # for i, a in enumerate(A[1:], 1):
        #     while q and i - q[0][0] > n:
        #         q.popleft()
        #     cur += a
        #     ans[i] = cur - q[0][1]
        #     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):
      # maximum non-empty subarray sum
      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:
        '''
        12341234
        limit of  len[] < a.length
        
        
        p[i], i
        
        '''
        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:
        def kadane(gen):
            ans = cur = -float('inf')
            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:
        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:
        '''
        12341234
        limit of  len[] < a.length
        
        
        p[i], i
        
        '''
        def kaden(gen):
            ans = cur = -float('inf')
            for n in gen:
                cur = n + max(0, cur)
                ans = max(ans, cur)
            return ans
        ans1 = kaden(iter(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:
        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
            
            size = len(gen)
            ans = cur = gen[0]
            for i in range(1,size):
                cur = max(gen[i], cur + gen[i])
                ans = max(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)
        A *= 2
        ans = [A[0]] + [0] * (len(A) - 1)
        q = collections.deque([(0, A[0])])
        cur = A[0]
        for i, a in enumerate(A[1:], 1):
            while q and i - q[0][0] > n:
                q.popleft()
            cur += a
            ans[i] = cur - q[0][1]
            while q and q[-1][1] >= cur:
                q.pop()
            q.append((i, cur))
        return max(ans)
        
        
        # 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:
        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)

        # Compute P[j] = sum(B[:j]) for the fixed array B = A+A
        P = [0]
        for _ in range(2):
            for x in A:
                P.append(P[-1] + x)

        # Want largest P[j] - P[i] with 1 <= j-i <= N
        # For each j, want smallest P[i] with i >= j-N
        ans = A[0]
        deque = collections.deque([0]) # i's, increasing by P[i]
        for j in range(1, len(P)):
            # If the smallest i is too small, remove it.
            if deque[0] < j-N:
                deque.popleft()

            # The optimal i is deque[0], for cand. answer P[j] - P[i].
            ans = max(ans, P[j] - P[deque[0]])

            # Remove any i1's with P[i2] <= P[i1].
            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:
        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:
        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:
        # find linear max subarray sum
        maxSum = A[0]
        curMaxSum = A[0]
        for i in range(1, len(A)):
            curMaxSum = max(curMaxSum + A[i], A[i])
            maxSum = max(maxSum, curMaxSum)
        
        # find linear min subarray sum
        minSum = A[0]
        curMinSum = A[0]
        for i in range(1, len(A)):
            curMinSum = min(curMinSum + A[i], A[i])
            minSum = min(minSum, curMinSum)
        
        # edge case: all values of A are negative
        if maxSum < 0:
            return maxSum
        
        # compare (linear max) with (total sum - linear min)
        return max(maxSum, sum(A)-minSum)


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]
            else:
                if 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):
        # compute pre(k)
        # maximum continuous subarray that ends at end of A and starts after k
        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])

        # compute regular dp
        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
#         min maxsum
#         0,6
        
        # 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
        # print(maxSum, total , minSum)
        # return max(maxSum, total - minSum) if maxSum > 0 else maxSum
#1 -2 3 -2
#  [-1,2,-3,2]
# cu -1  2  -1 1
# re. -1  2  2 2

# sum-min(subARR)
# SUM+MAX()


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        # there are two cases, one, includes end points, two, not include end points
        ans = float('-inf')
        csum = 0
        for x in A:
            csum = max(x,csum+x)
            ans = max(ans,csum)
            
        mi = float('inf')
        csum = 0 # notice that it can be zero
        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)
        #monotonic increasing array
        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):
        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:
        # case 1, kadane's algo
        totalSum = sum(A)
        curr = A[0]
        maxSum = A[0]
        
        for i in range(1, len(A)):
            
            curr = max(A[i] + curr, A[i])
            maxSum = max(maxSum, curr)
        
        # case 2, wrapping
        
        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:
        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:
        # Main idea: if we iterate over A twice to generate
        # a prefix array, then we can get subarrays in const
        # time by checking windows of size j - i <= len(A)
        
        # Once we have the prefix array, this problem reduces
        # to sliding window maximum (except we're looking for
        # the minimum). With the sliding window minimum, we 
        # can then update the result with 
        # result = max(result, curr_elem - minimum)
        
        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

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        N = len(A)

        # Compute P[j] = sum(B[:j]) for the fixed array B = A+A
        P = [0]
        for _ in range(2):
            for x in A:
                P.append(P[-1] + x)

        # Want largest P[j] - P[i] with 1 <= j-i <= N
        # For each j, want smallest P[i] with i >= j-N
        ans = A[0]
        deque = collections.deque([0]) # i's, increasing by P[i]
        for j in range(1, len(P)):
            # If the smallest i is too small, remove it.
            while deque[0] < j-N:
                deque.popleft()

            # The optimal i is deque[0], for cand. answer P[j] - P[i].
            ans = max(ans, P[j] - P[deque[0]])

            # Remove any i1's with P[i2] <= P[i1].
            while deque and P[j] <= P[deque[-1]]:
                deque.pop()

            deque.append(j)

        return ans


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:
        # normal kadane's algo
        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 and backward cumsum
        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
        
        # update opt estimates (if needed)
        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
        return max(opt)
        


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        N = len(A)

        # Compute P[j] = sum(B[:j]) for the fixed array B = A+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()

            # The optimal i is deque[0], for cand. answer P[j] - P[i].
            ans = max(ans, P[j] - P[deque[0]])

            # Remove any i1's with P[i2] <= P[i1].
            while deque and P[j] <= P[deque[-1]]:
                deque.pop()

            deque.append(j)

        return ans

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)
        #monoqueue dq that contains indices i such that P[i]s are non-decreasing
        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:
        n = len(A)
        B = [0]+A+A
        for i in range(1, len(B)):
            B[i] += B[i-1]
        maxv = B[1]
        
        stack = deque([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.popleft()
            maxv = max(num-B[stack[0]], maxv)
            #print(end, stack, maxv)
        if all(x<0 for x in A):
            return max(A)
        return maxv
                
                


class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        # edge case: all values of A are negative
        allNeg = True
        for i in A:
            if i > 0:
                allNeg = False
        if allNeg:
            return max(A)
        
        # find linear max subarray sum
        maxSum = A[0]
        curMaxSum = A[0]
        for i in range(1, len(A)):
            curMaxSum = max(curMaxSum + A[i], A[i])
            maxSum = max(maxSum, curMaxSum)
        
        # find linear min subarray sum
        minSum = A[0]
        curMinSum = A[0]
        for i in range(1, len(A)):
            curMinSum = min(curMinSum + A[i], A[i])
            minSum = min(minSum, curMinSum)
        
        # compare (linear max) with (total sum - linear min)
        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:
        '''
        Case 1. The first is that the subarray take only a middle part, and we know how to find the max subarray sum.
        Case2. The second is that the subarray take a part of head array and a part of tail array.
        
        in case two, you have two sub arrays, one at the front and one at the end. The middle segment actually now is the MIN
        subarray.
         The maximum result equals to the total sum minus the minimum subarray sum.
        '''
        total=0
        maxSum=A[0] #case1
        minSum=A[0] #case2
        curr_sum=0
        curr_sum_min=0
        for val in A:
            total+=val #calculate total sum\\
            #calculate max sum with kadanes normally for case1, assuming NO WRAP
            curr_sum=max(val,curr_sum+val)
            maxSum=max(maxSum,curr_sum)
            #now calculate the minsum
            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))) # min sum of the unwated sub array
        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