## Problem

## Key Idea

This problem is an advanced version of **[LeetCode] 53. Maximum Subarray**.

The only differnce is that the `nums`

array given is circular or not.

The target subarray can be in two forms:

**Wrapped around subarrays**

In this case, sum of the rest subarray in the middle always becomes minimum.

**Others**

Thus, we can calculate the maximum sum by `max(maxSubarraySum, totalSum-minSubarraySum)`

.

From left to right, calculate the `maxSubarraySum`

and `minSubarraySum`

individually, and calculate the ultimate answer.

- Time: \(O(N)\)
- Space: \(O(1)\)

Note

Think about this corner case: all the elements in`nums`

array are negative integers.

## Implementation

```
typedef vector<int> vi;
class Solution {
private:
const int NEG_INF= -1e5;
const int POS_INF= 1e5;
public:
int maxSubarraySumCircular(vi &nums) {
int n= nums.size(), totalSum= 0, maxSum= NEG_INF, minSum= POS_INF;
int curMax= NEG_INF, curMin= POS_INF;
for (int i=0; i < n; ++i) {
curMax= max(nums[i], curMax+nums[i]);
maxSum= max(maxSum, curMax);
curMin= min(nums[i], curMin+nums[i]);
minSum= min(minSum, curMin);
totalSum += nums[i];
}
if (maxSum < 0) return maxSum;
return max(maxSum, totalSum-minSum);
}
};
```

## Leave a comment