题目链接
题目描述
实现代码
思路:对于环形数组,其最大和就分为两种情况:
- 无环的最大子数组和;
- 有环的最大子数组和;
而对于有环的最大子数组和,其为首尾相接,因此我们找到无环的原始数组的最小子数组和,用数组元素的和减去该最小子数组和,即为第二种情况的解,两个进行对比取最大即可;
考虑极端情况,如果数组里的所有元素都为负数,那么就去最大元素即可,因此可以加一个数组最大元素的标记;
实现代码如下:
class Solution {
public int maxSubarraySumCircular(int[] A) {
int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
for (int a : A) {
curMax = Math.max(curMax + a, a);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(curMin + a, a);
minSum = Math.min(minSum, curMin);
total += a;
}
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
}