环形子数组的最大和【LC918】
给定一个长度为
n的环形整数数组nums，返回nums的非空 子数组 的最大可能和 。环形数组 意味着数组的末端将会与开头相连呈环状。形式上，
nums[i]的下一个元素是nums[(i + 1) % n]，nums[i]的前一个元素是nums[(i - 1 + n) % n]。子数组 最多只能包含固定缓冲区nums中的每个元素一次。形式上，对于子数组nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j其中k1 % n == k2 % n。
还好还有印象
- 思路：
2023/04/22
最大环形子数组的可能取值有两种：同53题非环形子数组之和或者环形子数组之和，因此我们可以分别求出两部分和的最大值，取其中的最大值即可
- 非环形子数组之和：采取贪心/dp策略，找到最大子数组之和，如果子数组之和为正数，那么继续向后寻找最大和；反之，如果子数组之和为负数，那么从下一个数开始找最大和
- 环形子数组之和：我们需要找到不相交的前缀子数组和后缀子数组和的最大值，可以转换为整个数组之和-子数组最小和，推导如下
- 该情况需要进行特判：当数组均为负数是，最小和是数组本身，那么环形子数组最大和为0，为错解，因此这种情况直接返回非环形子数组之和
- 实现
使用三目元算符代替max和min，提升效率
class Solution { public int maxSubarraySumCircular(int[] nums) { int n = nums.length; int sum = 0; int curMin = 0, curMax = 0; int minSum = Integer.MAX_VALUE; int maxSum = Integer.MIN_VALUE; for (int i = 0; i < n; i++){ // 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和 curMax = (curMax > 0 ? curMax : 0) + nums[i]; maxSum = maxSum > curMax ? maxSum : curMax; curMin = (curMax < 0 ? curMax : 0) + nums[i]; minSum = minSum < curMin ? minSum :curMin; sum += nums[i]; } if (minSum == sum){// 全部是负数 return maxSum; } return Math.max(maxSum, sum - minSum); } }
