# 918. Maximum Sum Circular Subarray
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
## Method 1: Dynamic Programming
### Idea:
- the circular subarray is the extension of LIS proble (longst increasing sequence)
- in this case, the problem can be devided in three situation:
	- the normal LIS (without circular case)
	- the dual problem (circular case): max (circular) = sum (all) - min (breaking)
	- all elements are negative: directly return the biggest element in array
	- 
```
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int num_max = A[0], num_min = A[0], sum = A[0];
        vector<int> dp_max = A, dp_min = A;
        for (int i = 1; i < A.size(); ++i) {
            // variation of Kanade Algo a + max(b, 0) -> max(a, b + a)
            dp_max[i] = max(dp_max[i], dp_max[i] + dp_max[i - 1]);
            dp_min[i] = min(dp_min[i], dp_min[i] + dp_min[i - 1]);
            num_max = max(num_max, dp_max[i]);
            num_min = min(num_min, dp_min[i]);
            sum += A[i];
        }
        // if all elements in array are negative, directly return the biggest one element
        if (num_max < 0) return num_max; 
        // otherwise, return the bigger result between LIS (num_max) and two subsequence (sum - min) 
        return max(sum - num_min, num_max);
    }
};
```
### Complexity Analysis
- Time complexity: O(n)
- Space complexity: O(n)