参考题解:https://leetcode.cn/problems/maximum-sum-circular-subarray/solutions/1152143/wo-hua-yi-bian-jiu-kan-dong-de-ti-jie-ni-892u/
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int sum = nums[0], minSum = nums[0], maxSum = nums[0];
int lastMin = nums[0], lastMax = nums[0];
for (int i = 1; i < n; ++i) {
sum += nums[i];
lastMin = Math.min(lastMin + nums[i], nums[i]);
lastMax = Math.max(lastMax + nums[i], nums[i]);
minSum = Math.min(lastMin, minSum);
maxSum = Math.max(lastMax, maxSum);
}
return maxSum > 0 ? Math.max(maxSum, sum - minSum) : maxSum;
}
}
这里注意最后返回的内容:
如果maxSum
小于0
,表示数组里一个正数元素都没有,那么sum - minSum
一定为0
,大于maxSum
,这显然是不对的,表示没有连续子数组长度为0
,因此要进行分类讨论。