larscheng
commented
2 months ago 思路
情况1:s1区间是最大和数组，不在环首尾交替处
[a1,a2][a3,a4,a5][a6,a7] |-----||---s1---||-----|
情况二: s3+s1是最大和数组，处在环首尾交替
[a1,a2,a3][a4][a5,a6,a7] |---s1---||s2||---s3---|
s1和s3构成了最大和数组，s2即位最小和数组 s1+s3=sum-s2，s2可以通过求最小和数组得来，sum可通过累加得来 特殊情况全是负数,-3,-2,-3,sum(-8)==min(-8),此时情况1=-2，情况2=max，无需计算
代码
public int maxSubarraySumCircular(int[] nums) {
int[] maxdp = new int[nums.length];
int[] mindp = new int[nums.length];
maxdp[0] = mindp[0] = nums[0];
int sum = nums[0];
int max = nums[0];
int min = nums[0];
for (int i = 1; i < nums.length ; i++) {
sum+=nums[i];
maxdp[i] = Math.max(nums[i],maxdp[i-1]+nums[i]);
max = Math.max(max,maxdp[i]);
mindp[i] = Math.min(nums[i],mindp[i-1]+nums[i]);
min = Math.min(min,mindp[i]);
}
return Math.max(max,sum==min?max:sum-min);
}
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
918. 环形子数组的最大和