45-最大子数组差
给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。注意事项
子数组最少包含一个数
样例
给出数组[1, 2, -3, 1]，返回 6
挑战
时间复杂度为O(n)，空间复杂度为O(n)
标签
贪心 枚举法 LintCode 版权所有 数组 子数组 前后遍历
思路
复用“求最大字数组和”的代码,求出从左自右遍历数的最大子数组maxLeft、最小子数组minLeft和从右自左遍历数的最大子数组maxRight、最小子数组minRight。然后求出maxLeft与minRight的最大差，minLeft与maxRight的最大差。即可得出最大子数组差。
code
class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer indicate the value of maximum difference between two
* Subarrays
*/
int maxDiffSubArrays(vector<int> nums) {
// write your code here
int size = nums.size(), i = 0;
int sum = 0, maxValue = 0;
int dec = 0, minValue = 0;
int *maxLeft = new int[size];
int *minLeft = new int[size];
int *maxRight = new int[size];
int *minRight = new int[size];
sum = maxValue = maxLeft[0] = nums[0];
for(i=1; i<size; i++) {
if(sum < 0) {
sum = nums[i];
}
else {
sum += nums[i];
}
if(sum > maxValue) {
maxValue = sum;
}
maxLeft[i] = maxValue;
}
sum = maxValue = maxRight[size-1] = nums[size-1];
for(i=size-2; i>=0; i--) {
if(sum < 0) {
sum = nums[i];
}
else {
sum += nums[i];
}
if(sum > maxValue) {
maxValue = sum;
}
maxRight[i] = maxValue;
}
dec = minValue = minLeft[0] = nums[0];
for(i=1; i<size; i++) {
if(dec > 0) {
dec = nums[i];
}
else {
dec += nums[i];
}
if(dec < minValue) {
minValue = dec;
}
minLeft[i] = minValue;
}
dec = minValue = minRight[size-1] = nums[size-1];
for(i=size-2; i>=0; i--) {
if(dec > 0) {
dec = nums[i];
}
else {
dec += nums[i];
}
if(dec < minValue) {
minValue = dec;
}
minRight[i] = minValue;
}
int result1 = 0x80000000;
int result2 = 0x80000000;
for(i=0; i<size-1; i++) {
result1 = (result1 > maxLeft[i]-minRight[i+1])?result1:( maxLeft[i]-minRight[i+1]);
result2 = (result2 > maxRight[i+1]-minLeft[i])?result2:( maxRight[i+1]-minLeft[i]);
}
delete[] maxLeft;
delete[] minLeft;
delete[] maxRight;
delete[] minRight;
return (result1 > result2)?result1:result2;
}
};