首页 > 代码库 > LintCode-Maximum Subarray Difference
LintCode-Maximum Subarray Difference
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.
Note
The subarray should contain at least one number
Example
For [1, 2, -3, 1], return 6
Challenge
O(n) time and O(n) space.
Solution:
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @return: An integer indicate the value of maximum difference between two 5 * Subarrays 6 */ 7 public int maxDiffSubArrays(ArrayList<Integer> nums) { 8 int len = nums.size(); 9 if (len==0) return 0;10 11 int[] leftMin = new int[len];12 int[] leftMax = new int[len];13 int endMin = nums.get(0), endMax = nums.get(0);14 leftMin[0] = endMin;15 leftMax[0] = endMax;16 for (int i=1;i<len;i++){17 //Calculate max subarray.18 endMax = Math.max(nums.get(i), nums.get(i)+endMax);19 leftMax[i] = Math.max(leftMax[i-1],endMax);20 21 //Calculate min subarray.22 endMin = Math.min(nums.get(i),nums.get(i)+endMin);23 leftMin[i] = Math.min(leftMin[i-1],endMin);24 }25 26 int[] rightMin = new int[len];27 int[] rightMax = new int[len];28 endMin = nums.get(len-1);29 endMax = nums.get(len-1);30 rightMin[len-1] = endMin;31 rightMax[len-1] = endMax;32 for (int i=len-2;i>=0;i--){33 endMax = Math.max(nums.get(i),nums.get(i)+endMax);34 rightMax[i] = Math.max(rightMax[i+1],endMax);35 endMin = Math.min(nums.get(i),nums.get(i)+endMin);36 rightMin[i] = Math.min(rightMin[i+1],endMin); 37 }38 39 int maxDiff= 0;40 for (int i=0;i<len-1;i++){41 if (maxDiff<Math.abs(leftMin[i]-rightMax[i+1]))42 maxDiff = Math.abs(leftMin[i]-rightMax[i+1]);43 44 if (maxDiff<Math.abs(leftMax[i]-rightMin[i+1]))45 maxDiff = Math.abs(leftMax[i]-rightMin[i+1]);46 }47 return maxDiff;48 49 50 }51 }
LintCode-Maximum Subarray Difference
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。