Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$

Question

Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

The sub-arrays should not overlap and it can not be empty.

eg [2 -1 -2 1 -4 2 8]

ans (-1 -2 1 -4) (2 8)

diff = 16

Better than $\mathcal O(n^2)$ solution was expected.

Answer 1

This is a complete re-edit of my previous solution, which erroneously focused on partitions, not on arbitrary sub-arrays.

This problem seems to be an interesting variation on the Maximum subarray problem, which consists of finding the subsequence of values with the largest sum in an array.

Given an array a of integers, finding the maximum subarray can be done as follows:

int best_left = 0, best_right = -1, best_sum = INT_MIN;
int i, curr_left = 0, curr_sum = 0;
for ( i = 0 ; i < N ; i++ ) {
    curr_sum += a[i];
    if ( curr_sum < a[curr_left] ) {
        curr_sum = 0;
        curr_left = i+1;
        }
    else if ( curr_sum > best_sum ) {
        best_left = curr_left;
        best_right = i;
        best_sum = curr_sum;
        }
    }

The above code is untested. The largest summing interval should then be [best_left,best_right].

To solve your problem, you could sweep from left to right and store the values best_left and best_sum for each position i in the array, effectively giving you the largest sub-array from 0 to i for each i.

At the same time, you could flip the signs in the above code and also store the minimum subarray from 0 to i for each i.

Now imagine doing the same thing again, yet this time traversing the array backwards, from right to left, also storing the minimum and maximum subarrays as you go along.

Once you've constructed both sets of indices, you can traverse them and find the point which partitions the array such that the difference between the minimum/maximum subarray on either side is largest.