public class Solution { public ArrayList<Integer> continuousSubarraySum(int[] A) { ArrayList<Integer> res = new ArrayList<Integer>(); if (A == null || A.length == 0) { return res; } int sum = A[0]; int max = sum; int start = 0, end = 0; res.add(0); res.add(0); for (int i = 1; i < A.length; i++) { if (sum > max) { res.set(0, start); res.set(1, i-1); max = sum; } if (sum < 0) { sum = 0; start = i; end = i; } sum += A[i]; } if (sum > max) { res.set(0, start); res.set(1, A.length-1); } return res; } }
Tag Archives: subarray
Lintcode: Maximum Subarray Difference
用到了max subarray的技巧,并且分别从左边和右边扫,对于每一个index, 更新res = Math.max(res, Math.max(maxFromRight[i] – minFromLeft[i-1], maxFromLeft[i] – maxFromRight[i-1]));
public class Solution { public int maxDiffSubArrays(ArrayList<Integer> nums) { if (nums == null || nums.size() == 0) { return 0; } int[] maxFromLeft = new int[nums.size()]; int[] minFromLeft = new int[nums.size()]; int min = nums.get(0); int max = min; int localmin = min; int localmax = max; maxFromLeft[0] = minFromLeft[0] = min; for (int i = 1; i < nums.size(); i++) { localmin = Math.min(nums.get(i), localmin+nums.get(i)); localmax = Math.max(nums.get(i), localmax+nums.get(i)); max = Math.max(max, localmax); min = Math.min(min, localmin); maxFromLeft[i] = max; minFromLeft[i] = min; } min = nums.get(nums.size() - 1); max = min; localmin = min; localmax = max; int res = Math.max(max - minFromLeft[nums.size()-2], maxFromLeft[nums.size() - 2] - min); for (int i = nums.size() - 2; i > 0; i--) { localmin = Math.min(nums.get(i), localmin+nums.get(i)); localmax = Math.max(nums.get(i), localmax+nums.get(i)); max = Math.max(max, localmax); min = Math.min(min, localmin); res = Math.max(res, Math.max(max - minFromLeft[i-1], maxFromLeft[i-1] - min)); } return res; } }
Lintcode: Maximum Subarray II
public class Solution { public int maxTwoSubArrays(ArrayList<Integer> nums) { if (nums == null || nums.size() == 0) { return 0; } int[] fromLeft = new int[nums.size()]; int[] fromRight = new int[nums.size()]; int global = Integer.MIN_VALUE; int local = 0; for (int i = 0; i < nums.size(); i++) { local = Math.max(nums.get(i), nums.get(i) + local); global = Math.max(global, local); fromLeft[i] = global; } local = 0; global = Integer.MIN_VALUE; for (int j = nums.size() - 1; j >= 0; j--) { local = Math.max(nums.get(j), nums.get(j) + local); global = Math.max(global, local); fromRight[j] = global; } local = Integer.MIN_VALUE; for (int i = 0; i < nums.size() - 1; i++) { local = Math.max(local, fromLeft[i] + fromRight[i+1]); } return local; } }