> For the complete documentation index, see [llms.txt](https://liuyang89116.gitbook.io/my-leetcode-book/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://liuyang89116.gitbook.io/my-leetcode-book/chapter_8_high_frequency/subarray-sum/problem_maximum_subarray_difference_lintcode.md).

# Problem: Maximum Subarray Difference (LintCode)

> <http://www.lintcode.com/en/problem/maximum-subarray-difference/>

## 思路

* 这道题实际上是两次买卖股票的升级版。
* 绝对值之差的最大值的实质是什么？ |A - B| 的最大值，就是**A最大**，B 要非常小，换句话说，就&#x662F;**(-B)也要最大**。
* 那么思路就很好理解了，找到`left[]`的最小值和最大值，找到`right[]`的最小值和最大值。相当于进行四次 Maximum Subarray

```java
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two
     *          Subarrays
     */
    public int maxDiffSubArrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int size = nums.length;
        int[] left_min = new int[size];
        int[] left_max = new int[size];
        int[] right_min = new int[size];
        int[] right_max = new int[size];
        int[] copy = new int[size];

        for (int i = 0; i < size; i++) {
            copy[i] = -1 * nums[i];
        }


        // left_max
        int sum = 0, minSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) {
            sum += nums[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            left_max[i] = max;
        }

        // right_max
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for (int i = size - 1; i >= 0; i--) {
            sum += nums[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            right_max[i] = max;
        }

        // left_min
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) {
            sum += copy[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            left_min[i] = -1 * max;
        }

        //right_min
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for (int i = size - 1; i >= 0; i--) {
            sum += copy[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            right_min[i] = -1 * max;
        }

        int diff = 0;
        int left = Integer.MIN_VALUE, right = Integer.MIN_VALUE;
        for (int i = 0; i < size - 1; i++) {
            diff = Math.max(diff, Math.abs(left_max[i] - right_min[i + 1]));
            diff = Math.max(diff, Math.abs(left_min[i] - right_max[i + 1]));
        }

        return diff;
    }
}
```

## 思路

1. 最后求最大值

   ```java
   int diff = 0;
   int left = Integer.MIN_VALUE, right = Integer.MIN_VALUE;
   for (int i = 0; i < size - 1; i++) {
          diff = Math.max(diff, Math.abs(left_max[i] - right_min[i + 1]));
          diff = Math.max(diff, Math.abs(left_min[i] - right_max[i + 1]));
   }
   ```

   方法一定是：**左边的最小 - 右边的最大；左边的最大 - 右边的最小**。之前犯错的原因是：左边的最小 - 右边的最大；右边的最大 - 左边的最小。结果看似是两行语句，实际上办的是一件事儿！所以永远从左边出发，这样不容易错。
2. Maximum Subarray 的核心一定要熟练

   ```java
   // left_max
   int sum = 0, minSum = 0;
   int max = Integer.MIN_VALUE;
   for (int i = 0; i < size; i++) {
        sum += nums[i];
        max = Math.max(max, sum - minSum);
        minSum = Math.min(minSum, sum);
        left_max[i] = max;
   }
   ```
3. 求最小值的时候，最后给 max 乘 -1再变回最小

   ```java
   sum = 0;
   minSum = 0;
   max = Integer.MIN_VALUE;
   for (int i = 0; i < size; i++) {
        sum += copy[i];
        max = Math.max(max, sum - minSum);
        minSum = Math.min(minSum, sum);
        left_min[i] = -1 * max;
   }
   ```