给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。

返回这个最大的差值。

您在真实的面试中是否遇到过这个题？ 

Yes

例子

给出数组[1, 2, -3, 1]。返回 6

注意

子数组最少包括一个数

挑战

时间复杂度为O(n)。空间复杂度为O(n)

标签 

相关题目 

分析：这题还是有点难度的感觉，首先直觉是能够套用求最大字数组和的代码，其次。求差的绝对值最大，那么求出子数组和的最大最小值。然后相减即可，可是有可能是左边最大右边最小，也可能是左边最小右边最大。

代码：

class Solution {public:    /**     * @param nums: A list of integers     * @return: An integer indicate the value of maximum difference between two     *          Subarrays     */    int maxDiffSubArrays(vector
     
       nums) {        // write your code here        int x1 = deal(nums);        reverse(nums.begin(),nums.end());        int x2 = deal(nums);        return max(x1,x2);    }    int deal(vector
      
        nums)    {        int n = nums.size();        vector
       
         leftMax(n,0);        vector
        
          rightMin(n,0);        int sum = 0;        int mx = INT_MIN;        for(int i=0;i
         
          =0;i--)        {            sum+=nums[i];            mx = min(sum,mx);            if(sum>0)                sum = 0;            rightMin[i]=mx;        }        int ret = 0;        for(int i=1;i