[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)，代码如下：

	class Solution {
	public:
	int maxSubarraySumCircular(vector<int>& A) {
	int len = A.size(), currMax = INT_MIN, res = INT_MIN, preSum = 0;
	//max presum in [0, i]
	vector<int> maxLeft(len, INT_MIN);
	for (int i = 0; i < len; ++i)
	{
	preSum += A[i];
	maxLeft[i] = i ? max(maxLeft[i - 1], preSum) : preSum;
	currMax = max(0, currMax) + A[i];
	res = max(res, currMax);
	}
	int suffixSum = 0;
	for (int i = len - 1; i > 0; --i)
	{
	suffixSum += A[i];
	res = max(res, suffixSum + maxLeft[i - 1]);
	}
	return res;
	}
	};

view raw Maximum Sum Circular Subarray_1.cpp hosted with ❤ by GitHub

如果我们从另外一个角度思考，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)，常数空间，代码如下：

	class Solution {
	public:
	int maxSubarraySumCircular(vector<int>& A) {
	int len = A.size(), currMax = INT_MIN, res = INT_MIN, sum = 0;
	//regular dp
	for (int i = 0; i < len; ++i)
	{
	sum += A[i];
	currMax = max(0, currMax) + A[i];
	res = max(res, currMax);
	}
	//reverse sign
	int tmp = INT_MIN;
	for (auto& num : A)num = -num;
	currMax = INT_MIN;
	for (int i = 0; i < len - 1; ++i)
	{
	currMax = max(0, currMax) + A[i];
	tmp = max(tmp, currMax);
	}
	currMax = INT_MIN;
	for (int i = len - 1; i > 0; --i)
	{
	currMax = max(0, currMax) + A[i];
	tmp = max(tmp, currMax);
	}
	return max(res, sum + tmp);
	}
	};

view raw Maximum Sum Circular Subarray_2.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	int maxSubarraySumCircular(vector<int>& A) {
	int len = A.size();
	vector<int> presums(2 * len + 1, 0);
	for (int i = 0; i < 2 * len; ++i)
	presums[i + 1] = presums[i] + A[i % len];
	deque<int> dq;
	int res = INT_MIN;
	for (int i = 0; i < 2 * len; ++i)
	{
	while (dq.size() && i - dq.front() > len)dq.pop_front();
	if (dq.size() && dq.front() > len)break;
	if (dq.size())res = max(res, presums[i] - presums[dq.front()]);
	while (dq.size() && presums[dq.back()] >= presums[i])
	dq.pop_back();
	dq.push_back(i);
	}
	return res;
	}
	};

view raw Maximum Sum Circular Subarray_3.cpp hosted with ❤ by GitHub