首页 > 代码库 > 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