[LintCode] Maximum Subarray Difference

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.

Example

For [1, 2, -3, 1], return 6

Note

The subarray should contain at least one number

Challenge

O(n) time and O(n) space.

左右两头扫，注意要分别记录左边最大子段和、最小子段和，右边最大子段和、最小子段和。

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums: A list of integers
 5      * @return: An integer indicate the value of maximum difference between two
 6      *          Subarrays
 7      */
 8     int maxDiffSubArrays(vector<int> nums) {
 9         // write your code here
10         if (nums.empty()) return -1;
11         int N = nums.size();
12         vector<int> max_sum_l(N), min_sum_l(N);
13         int max_tmp = nums[0], min_tmp = nums[0];
14         max_sum_l[0] = min_sum_l[0] = nums[0];
15         for (int i = 1; i < N; ++i) {
16             max_tmp = max(max_tmp + nums[i], nums[i]);
17             min_tmp = min(min_tmp + nums[i], nums[i]);
18             max_sum_l[i] = max(max_tmp, max_sum_l[i-1]);
19             min_sum_l[i] = min(min_tmp, min_sum_l[i-1]);
20         }
21         vector<int> max_sum_r(N), min_sum_r(N);
22         max_tmp = min_tmp = nums[N-1];
23         max_sum_r[N-1] = min_sum_r[N-1] = nums[N-1];
24         for (int i = N - 2; i >= 0; --i) {
25             max_tmp = max(max_tmp + nums[i], nums[i]);
26             min_tmp = min(min_tmp + nums[i], nums[i]);
27             max_sum_r[i] = max(max_tmp, max_sum_r[i+1]);
28             min_sum_r[i] = min(min_tmp, min_sum_r[i+1]);
29         }
30         int res = 0;
31         for (int i = 0; i < N - 1; ++i) {
32             res = max(res, abs(max_sum_l[i] - min_sum_r[i+1]));
33             res = max(res, abs(min_sum_l[i] - max_sum_r[i+1]));
34         }
35         return res;
36     }
37 };