45. Maximum Subarray Difference

Leave a comment

August 21, 2016 by oneOokay

这一题感觉应该要多练习吧,因为他结合了maximum subarray 和 minmum subarray的解法。

//scan twice
//1. left from right: leftmin[] and leftmax[]
//2. right from left: rightmin[] and rightmax[]
//for loop:
// max(right[max] – left[min], leftmax[i] – rightmin[i])

public int maxDiffSubArrays(int[] nums) {
// write your code here
if (nums == null || nums.length <=1) {
return 0;
}

int len = nums.length;
int[] leftmin = new int[len];
int[] leftmax = new int[len];
int[] rightmin = new int[len];
int[] rightmax = new int[len];

int minSum = 0;
int maxSum = 0;
int sum = 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
//first scan: left to right
for (int i = 0; i < len; i ++) {
sum += nums[i];
max = Math.max(max, sum – minSum);
minSum = Math.min(sum, minSum);
leftmax[i] = max;

min = Math.min(min, sum – maxSum);
maxSum = Math.max(sum, maxSum);
leftmin[i] = min;
}

sum = 0;
minSum = 0;
maxSum = 0;
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
for (int i = len – 1; i >= 0; i –) {
sum += nums[i];
max = Math.max(max, sum – minSum);
minSum = Math.min(sum, minSum);
rightmax[i] = max;

min = Math.min(min, sum – maxSum);
maxSum = Math.max(sum, maxSum);
rightmin[i] = min;
}

max = 0;
for (int i = 0; i < len – 1; i ++) {
max = Math.max(max, Math.max(Math.abs(leftmax[i] – rightmin[i + 1]), Math.abs(rightmax[i + 1] – leftmin[i]))); //注意这里不要忘记了把max自身也放在里面。。。
}
return max;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: