Maximum Sum Circular Subarray
给一个数组, 求最大循环子数组.
通过观察得知, 这题的答案是在普通的最大子数组问题和循环子数组问题的两个答案下取最大.
前者我们已经有算法可解. 后者通过观察得知, 如果循环数组的答案包含了数字中第一项或者最后一项, 那么这个答案已经在前者(普通)的计算中算过了. 故得知, 循环数组的最大子数组的答案等于数组的和在第二个元素和倒数第二个元素的最小和子数组。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Solution { public int maxSubarraySumCircular(int[] nums) { int maxsub = maxSub(nums); int sum = sum(nums); int minsub = minSub(nums); return Math.max(maxsub, sum - minsub); } public int maxSub(int[] nums){ int l = 0; int g = Integer.MIN_VALUE/2; for(int n : nums){ l += n; g = Math.max(l,g); if(l < 0) l = 0; } return g; } public int sum(int[] nums){ int sum = 0; for(int n : nums) sum += n; return sum; } public int minSub(int[] nums){ int l = 0; int g = Integer.MAX_VALUE / 2; for(int i = 1; i < nums.length - 1; i++){ l += nums[i]; g = Math.min(l,g); if(l > 0) l = 0; } return g; } } |