# Maximum Sum Circular Subarray

## Problem

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 <= k_1, k_2 <= j$ with$k_1 mod A.length = k_2 mod A.length$.)

### Examples

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


### Notes

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

## 暴力法

### 最大子序列和算法

 1 2 3 4 5 6 7  def kadane(arr): if len(arr) == 0: return 0 ans = cur = arr[0] for i in arr[1:]: cur = arr[i] + max(cur, 0) ans = max(ans, cur) return ans 

 1  dp[i+1] = dp[i] + arr[i+1] if dp[i] > 0 else arr[i+1] 

### 问题进一步分析

#### 相邻数组法

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  def fun1(A): ans = cur = A[0] N = len(A) for i in range(1,N): cur = A[i] + max(0,cur) ans = max(ans,cur) leftsums = [A[0] for _ in range(N)] for i in range(1,N): leftsums[i] = leftsums[i-1] + A[i] rightsums = [A[-1] for _ in range(N)] maxright = [A[-1] for _ in range(N)] for i in range(N-2,-1,-1): rightsums[i] = rightsums[i+1] + A[i] maxright[i] = max(maxright[i+1],rightsums[i]) for i in range(1,N-1): ans = max(ans, leftsums[i-1]+maxright[i]) return ans 

#### 变号法

  1 2 3 4 5 6 7 8 9 10 11 12 13  def fun2(A): def kadane(gen): if len(gen) == 0: return 0 ans = cur = gen[0] for i in gen[1:]: cur = i + max(cur,0) ans = max(ans,cur) return ans alls = sum(A) ans1 = kadane(A) ans2 = alls + kadane([-A[i] for i in range(1,len(A)-1)]) return max(ans1,ans2) 

#### 前缀和+优先队列

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  def fun(A): P = A * 2 for i in range(1,len(P)): P[i] = P[i] + P[i-1] from collections import deque queue = deque([0]) ans = A[0] for j in range(1,len(P)): i = queue[0] while j - i > len(A): queue.popleft() i = queue[0] ans = max(ans, P[j] - P[i]) while queue and P[queue[-1]] > P[j]: queue.pop() queue.append(j) return ans