Maximum Absolute Sum of Any Subarray
给一个array, 求最大绝对值子数组的和是多少.
绝对值就是既要看最大和子数组, 也要看最小和(负数)子数组.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public int maxAbsoluteSum(int[] nums) { int maxSum = Integer.MIN_VALUE; int cur = 0; for(int i = 0; i < nums.length; i++) { cur += nums[i]; if(cur < 0) cur = 0; maxSum = Math.max(maxSum, cur); } int maxMin = Integer.MAX_VALUE; cur = 0; for(int i = 0; i < nums.length; i++) { cur += nums[i]; if(cur > 0) cur = 0; maxMin = Math.min(maxMin, cur); } return Math.max(maxSum, Math.abs(maxMin)); } } |