#include <iostream>

#include <algorithm>

#include <climits>

using namespace std;

// Fill aux[k] with of sub-array A(0, k) if diff is 1 or

// maximum sum of sub-array A(k, n-1) if diff is -1, using Kadane17;s algorithm

// diff –> counter for loop from i to j in A[] (diff can be +1 or -1)

void maxSumSubarray(int A[], int aux[], int i, int j, int diff)

{

int max_so_far = A[i];

int max_ending_here = A[i];

aux[i] = A[i];

for (int k = i + diff; k != j; k += diff)

{

// update maximum sum of sub-array “ending” or “starting” at index k

max_ending_here = max(A[k], max_ending_here + A[k]);

// update result if current sub-array sum is found to be greater

max_so_far = max(max_so_far, max_ending_here);

aux[k] = max_so_far;

}

}

void fillArrays(int A[], int left_max[], int right_max[],

int left_min[], int right_min[], int n) {

maxSumSubarray(A, left_max, 0, n 1, 1);

maxSumSubarray(A, right_max, n 1, 0, 1);

// negate A[] for finding the minimum sum of sub-arrays using

// the same logic for finding maximum sum of sub-arrays

transform(A, A + n, A, negate<int>());

/* transform() is equivalent to

for (int i = 0; i < n; i++)

A[i] = -A[i]; */

maxSumSubarray(A, left_min, 0, n 1, 1);

maxSumSubarray(A, right_min, n 1, 0, 1);

// negate left_min[] and right_min[] to get minimum sum of sub-arrays

transform(left_min, left_min + n, left_min, negate<int>());

transform(right_min, right_min + n, right_min, negate<int>());

// restore the sign of A[]

transform(A, A + n, A, negate<int>());

}

// maximum between the sum of elements of

// two non-overlapping sub-arrays in given array

int maxAbsDiff(int A[], int n)

{

// left_max[i] stores maximum sum of sub-array in A(0, i)

// right_max[i] stores maximum sum of sub-array in A(i, n-1)

// left_min[i] stores minimum sum of sub-array in A(0, i)

// right_min[i] stores minimum sum of sub-array in A(i, n-1)

int left_max[n], right_max[n], left_min[n], right_min[n];

fillArrays(A, left_max, right_max, left_min, right_min, n);

// stores maximum absolute difference

int max_abs_diff = INT_MIN;

// do for each index i of the array

for (int i = 0; i < n 1; i++) {

max_abs_diff = max(max_abs_diff, max(abs(left_max[i] right_min[i+1]),

abs(left_min[i] right_max[i+1])));

}

return max_abs_diff;

}

int main()

{

int A[] = { 3, 2, 6, 3, 5, 9, 3, 4, 1, 8, 2 };

int n = sizeof(A) / sizeof(A[0]);

cout << “The maximum absolute difference is “ << maxAbsDiff(A, n);

return 0;

}