福州手机建站模板_建筑工程网络软件_网络营销策划的内容_站长之家网站模板

Problem: 918. 环形子数组的最大和

👨‍🏫 参考题解

⏰ 时间复杂度：$O(n)$
🌎 空间复杂度：$O(1)$

class Solution {public int maxSubarraySumCircular(int[] nums) {int maxSum = Integer.MIN_VALUE; // 最大子数组和，不能为空int minSum = 0; // 最小子数组和，可以为空//在非循环数组下，max 是当前得出的最大子数组和，min 是最小子数组和int max = 0, min = 0, sum = 0;// sum 是总和for (int x : nums) {// 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和max = Math.max(max, 0) + x;maxSum = Math.max(maxSum, max);// 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和min = Math.min(min, 0) + x;minSum = Math.min(minSum, min);sum += x;}// sum == minSum 时表明最小子数组是整个数组（数组元素全是负数的情况）// sum - minSum 为跨越边界的最大子数组和return sum == minSum ? maxSum : Math.max(maxSum, sum - minSum);}
}