Lintcode: Maximum Subarray Difference - neverlandly - 博客园
For
O(n) time and O(n) space:
http://pulala52.blogspot.com/2017/06/lintcode45-maximum-subarray-difference.html
两次遍历，从左到右和从右到左。用两个数组leftMin[i], LeftMax[i]保存左侧到当前位置i的最大子数组和最小子数组的值，再从右往左遍历找到右侧当前位置的最大子数组和最小子数组的值。
这道题的解法是max subarray，min subarray，max subarray II的结合，不细说了，注意左边要维护两个数组分别是globalMax和globalMin，右边时候同理的，localMax和localMin，DP方程参考之前的题目，时间复杂度O(n)，空间复杂度O(n)
思路很简单，写起来很烦躁。分别左右两边求连续最大最小值，相当于把maximum subarray写四遍。。。然后比较leftMax-rightMin vs rightMax - leftMin
把数组分成两部分，可以从i和i+1(0<= i < len-1)之间分开，a[0, i] a[i+1, len-1]，然后分别求两个子数组中的最大子段和，以及最小字段和，然后求差的最大值即可。
http://blog.csdn.net/nicaishibiantai/article/details/44490241
Read full article from Lintcode: Maximum Subarray Difference - neverlandly - 博客园
Given an array with integers.
Find two non-overlapping subarrays A and B, which
|SUM(A) - SUM(B)| is the largest.
Return the largest difference.
Notice
The subarray should contain at least one number
[1, 2, -3, 1], return 6.O(n) time and O(n) space:
http://pulala52.blogspot.com/2017/06/lintcode45-maximum-subarray-difference.html
这道题的解法是max subarray，min subarray，max subarray II的结合，不细说了，注意左边要维护两个数组分别是globalMax和globalMin，右边时候同理的，localMax和localMin，DP方程参考之前的题目，时间复杂度O(n)，空间复杂度O(n)
http://blog.csdn.net/gqk289/article/details/68958119两次遍历，从左到右和从右到左。用两个数组leftMin[i], LeftMax[i]保存左侧到当前位置i的最大子数组和最小子数组的值，再从右往左遍历找到右侧当前位置的最大子数组和最小子数组的值。
- public int maxDiffSubArrays(int[] nums) {
- if (nums == null || nums.length == 0) {
- return 0;
- }
- int n = nums.length;
- int[] leftMin = new int[n + 1];
- int[] leftMax = new int[n + 1];
- leftMin[0] = Integer.MAX_VALUE;
- leftMax[0] = Integer.MIN_VALUE;
- int curMin = 0;
- int curMax = 0;
- for (int i = 0; i < n; i++) {
- curMin = Math.min(nums[i], curMin + nums[i]);
- curMax = Math.max(nums[i], curMax + nums[i]);
- leftMax[i + 1] = Math.max(leftMax[i], curMax);
- leftMin[i + 1] = Math.min(leftMin[i], curMin);
- }
- int res = 0;
- curMin = 0;
- curMax = 0;
- int max = Integer.MIN_VALUE;
- int min = Integer.MAX_VALUE;
- for (int i = n - 1; i > 0; i--) {
- curMax = Math.max(nums[i], curMax + nums[i]);
- curMin = Math.min(nums[i], curMin + nums[i]);
- max = Math.max(max, curMax);
- min = Math.min(min, curMin);
- res = Math.max(res, Math.max(Math.abs(max - leftMin[i]), Math.abs(leftMax[i] - min)));
- }
- return res;
- }
public int maxDiffSubArrays(int[] nums) { // write your code here int size = nums.length; int[] left_max = new int[size]; int[] left_min = new int[size]; int[] right_max = new int[size]; int[] right_min = new int[size]; int[] copy = new int[size]; /*Get negative copy*/ for(int i = 0; i < size; i++){ copy[i] = -1 * nums[i]; } int max = Integer.MIN_VALUE; int sum = 0; int minSum = 0; /*Forward: get max subarray*/ for(int i = 0; i < size; i++){ sum += nums[i]; max = Math.max(max, sum - minSum); minSum = Math.min(sum, minSum); left_max[i] = max; } /*Backward: get max subarray*/ max = Integer.MIN_VALUE; sum = 0; minSum = 0; for(int i = size - 1; i >= 0; i--){ sum += nums[i]; max = Math.max(max, sum - minSum); minSum = Math.min(sum, minSum); right_max[i] = max; } /*Forward: get min subarray*/ max = Integer.MIN_VALUE; sum = 0; minSum = 0; for(int i = 0; i < size; i++){ sum += copy[i]; max = Math.max(max, sum - minSum); minSum = Math.min(sum, minSum); left_min[i] = -1 * max; } /*Backward: get min subarray*/ max = Integer.MIN_VALUE; sum = 0; minSum = 0; for(int i = size - 1; i >= 0; i--){ sum += copy[i]; max = Math.max(max, sum - minSum); minSum = Math.min(sum, minSum); right_min[i] = -1 * max; } int diff = 0; for(int i = 0; i < size - 1; i++){ diff = Math.max(diff, Math.abs(left_max[i] - right_min[i + 1])); diff = Math.max(diff, Math.abs(left_min[i] - right_max[i + 1])); } return diff; }http://www.jianshu.com/p/ad189dfc8191
- 枚举分割线，但本题每次要知道分割线左边和右边的最大/最小数组和
- 枚举一遍分割线，求max( abs(左最大-右最小), abs(左最小-右最大) )
这道题的解法是max subarray，min subarray，max subarray II的结合，不细说了，注意左边要维护两个数组分别是globalMax和globalMin，右边时候同理的，localMax和localMin，DP方程参考之前的题目，时间复杂度O(n)，空间复杂度O(n)
思路很简单，写起来很烦躁。分别左右两边求连续最大最小值，相当于把maximum subarray写四遍。。。然后比较leftMax-rightMin vs rightMax - leftMin
把数组分成两部分，可以从i和i+1(0<= i < len-1)之间分开，a[0, i] a[i+1, len-1]，然后分别求两个子数组中的最大子段和，以及最小字段和，然后求差的最大值即可。
public int maxDiffSubArrays(ArrayList<Integer> nums) { 8 // write your code 9 if (nums==null || nums.size()==0) return 0; 10 int len = nums.size(); 11 int[] lGlobalMax = new int[len]; 12 int[] lGlobalMin = new int[len]; 13 int lLocalMax = nums.get(0); 14 int lLocalMin = nums.get(0); 15 lGlobalMax[0] = lLocalMax; 16 lGlobalMin[0] = lLocalMin; 17 for (int i=1; i<len; i++) { 18 lLocalMax = Math.max(lLocalMax+nums.get(i), nums.get(i)); 19 lGlobalMax[i] = Math.max(lLocalMax, lGlobalMax[i-1]); 20 21 lLocalMin = Math.min(lLocalMin+nums.get(i), nums.get(i)); 22 lGlobalMin[i] = Math.min(lLocalMin, lGlobalMin[i-1]); 23 } 24 25 int[] rGlobalMax = new int[len]; 26 int[] rGlobalMin = new int[len]; 27 int rLocalMax = nums.get(len-1); 28 int rLocalMin = nums.get(len-1); 29 rGlobalMax[len-1] = rLocalMax; 30 rGlobalMin[len-1] = rLocalMin; 31 for (int i=len-2; i>=0; i--) { 32 rLocalMax = Math.max(rLocalMax+nums.get(i), nums.get(i)); 33 rGlobalMax[i] = Math.max(rLocalMax, rGlobalMax[i+1]); 34 35 rLocalMin = Math.min(rLocalMin+nums.get(i), nums.get(i)); 36 rGlobalMin[i] = Math.min(rLocalMin, rGlobalMin[i+1]); 37 } 38 39 int maxDiff = Integer.MIN_VALUE; 40 for (int i=0; i<len-1; i++) { 41 if (maxDiff < Math.abs(lGlobalMax[i]-rGlobalMin[i+1])) 42 maxDiff = Math.abs(lGlobalMax[i]-rGlobalMin[i+1]); 43 44 45 if (maxDiff < Math.abs(lGlobalMin[i]-rGlobalMax[i+1])) 46 maxDiff = Math.abs(lGlobalMin[i]-rGlobalMax[i+1]); 47 } 48 return maxDiff; 49 }Space Optimization:
http://blog.csdn.net/nicaishibiantai/article/details/44490241
public int maxDiffSubArrays(ArrayList<Integer> nums) {
int max = Integer.MIN_VALUE;
if (nums.size() <2) {
return 0;
}
int n = nums.size();
int[] leftMax = new int[n], leftMin = new int[n],
int localMax = 0; int localMin = 0;
for (int i = 0; i < n; i++) {
int num = nums.get(i);
localMax = Math.max(num + localMax, num);
localMin = Math.min(num + localMin, num);
if (i == 0) {
leftMax[i] = localMax;
leftMin[i] = localMin;
} else {
leftMax[i] = Math.max(localMax, leftMax[i-1]);
leftMin[i] = Math.min(localMin, leftMin[i-1]);
}
}
localMax = 0; localMin = 0;
int lastMax = 0, lastMin = 0;
for (int i = n-1; i > 0; i--) {
int num = nums.get(i);
localMax = Math.max(num + localMax, num);
localMin = Math.min(num + localMin, num);
if (i == n-1) {
lastMax = localMax;
lastMin = localMin;
} else {
lastMax = Math.max(localMax, lastMax);
lastMin = Math.min(localMin, lastMin);
}
max = Math.max(Math.max(Math.abs(leftMax[i-1]-lastMin),
Math.abs(lastMax - leftMin[i-1])), max);
}
return max;
}
http://hehejun.blogspot.com/2015/01/lintcodemaximum-subarray-difference.htmlRead full article from Lintcode: Maximum Subarray Difference - neverlandly - 博客园
