[LeetCode]Maximum Sum Circular Subarray

和普通的Max Subarray的区别就是这里是环形的，也就是说，除了普通的subarray之外，我们还要考虑A[0: i]，A[j : len - 1]组成的subarray的最大值，其中i < j。求解这个问题的话，我们可以建立一个maxLeft数组，其中maxLeft[i]表示A[0 : i]区间中左边界在A[0]处的最大subarray；同样的我们从右边开始扫，结合maxLeft[i]来求出A[0: i]，A[j : len - 1]组成的subarray的最大值。时间复杂度，空间复杂度O(N)，代码如下：

如果我们从另外一个角度思考，A[0: i]，A[j : len - 1]组成的subarray的subarray的和，其中i < j，其实就相当于数组的和sum，减去A[i + 1 : j - 1]的结果。那么我们把所有元素乘以-1，然后计算普通的非环形的max subarray即可，最后结果就为sum + max subarray，注意为了避免max subarray就是整个数组的情况，我们分别计算A[1 : len - 1]和A[0, len - 2]的情况。时间复杂度O(N)，常数空间，代码如下：

还有一种方法，和Shortest Subarray with Sum at Least K十分类似，我们也是维护一个递增的presum序列，序列里存的都是可能作为区间起始位置的地方，我们可以注意到，如果存在i < j并且presum[i] >= presum[j]那么i显然不可能是比j更为优秀的起点，我们pop出来，所以序列里维护的是递增序列，同时由于subarray的长度不可能超过N，我们需要在序列头部pop出所有"过期"的元素。时间复杂度，空间复杂度O(N)，代码如下：