给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
动态规划
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> leftMax(n);int pre = nums[0], res = nums[0], leftSum = nums[0] ;leftMax[0] = nums[0];for(int i = 1; i < n; i++){pre = max(nums[i], pre + nums[i]);res = max(res, pre);leftSum += nums[i];leftMax[i] = max(leftMax[i-1], leftSum);}int rightSum = 0;for(int i = n - 1; i > 0 ; i--){rightSum += nums[i];res = max(res, rightSum + leftMax[i-1]);}return res;}
};
时间复杂度：O(n)，其中 n 是 nums 的长度。求解第一种情况的时间复杂度为 O(n)，求解 leftMax 数组和枚举后缀的时间复杂度为 O(n)，因此总的时间复杂度为 O(n)。
空间复杂度：O(n)，其中 n 是 nums 的长度。过程中我们使用 leftMax 来存放最大前缀和。
用动态规划的思路来讲，是要列出可能的情况。在这道题中一种情况是不跨越尾部，也就是正常的子段，另外一种是跨越尾部。针对特殊的跨越尾部的情况，使用leftMax来记录第 i 个元素之前的最大子段和，然后从右到左遍历数组，最后比较两种情况的最大值即可。
取反
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();int sum = nums[0];int preMax = nums[0], resMax = nums[0];int preMin = nums[0], resMin = nums[0];for(int i = 1; i < n; i++){preMax = max(nums[i], preMax + nums[i]);resMax = max(resMax, preMax);preMin = min(nums[i], preMin + nums[i]);resMin = min(resMin, preMin);sum += nums[i];}if(resMax < 0){return resMax;}else{return max(resMax, sum - resMin);}}
};
时间复杂度：O(n)，其中 n 是 nums 的长度。
空间复杂度：O(1)。过程中只是用到了常数个变量。
这是一个更加巧妙的思路，并且有更低的空间复杂度。他的思想是所有数组元素之和减去中间的一段最小子段和，剩下的部分就是最大的经过头尾的子段和，再与正常子段和比较即可。要注意的是，当resMax < 0 的时候，sum - resMin返回的是一个空数组，这时候只要返回resMax。
