CareerCup

An O(n) solution is possible.

We consider all "split points", i.e. points such that one subarray lies to the left of it, and one to the right, and compute the best for each possible split point.

Dynamic programming works.

Given Array A[1,...n]

Using the standard dynamic programming algorithm, we can compute for a given i, the maximum and minimum sum subarrays in A[1...i] and A[i+1 ... n]. Note that the point between i and i+1 is a split point.

This can be done by making two passes once from 1 to n, and other from n to 1 and give us four arrays with the max and min sub-array sums.

Now given the above four arrays, for split point between i and i+1, we can take the max and min combinations (max from right, min from left and max from left, min from left), and get the combination which gives the better result.

Once we have the max for each split point, we get the global optimum.

O(n) time, O(n) space.

Use dp with kadane's algorithm for solving above problem...:-)

import java.io.*;
public class Main {

public static void main(String args[]) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
long a[]=new long[10000];
long b[]=new long[10000];
long max1[]=new long[10000];
long min1[]=new long[10000];
long max2[]=new long[10000];
long min2[]=new long[10000];
int n=Integer.parseInt(br.readLine());
String arr[]=br.readLine().split(" " );
int i=0;
for(String s:arr)
{
a[i]=Integer.parseInt(arr[i]);
b[i]=-a[i];
i++;
}

long maxsofar=a[0],maxendinghere=a[0];max1[0]=a[0];
for(i=1;i<n;i++)
{
//maxendinghere=maxendinghere+a[i]>0?maxendinghere+a[i]:0;
maxendinghere=maxendinghere+a[i];
maxendinghere=maxendinghere>a[i]?maxendinghere:a[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
max1[i]=maxsofar;
}
max2[n-1]=maxendinghere=maxsofar=a[n-1];
for(i=n-2;i>=0;i--)
{
//maxendinghere=maxendinghere+a[i]>0?maxendinghere+a[i]:0;
maxendinghere=maxendinghere+a[i];
maxendinghere=maxendinghere>a[i]?maxendinghere:a[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
max2[i]=maxsofar;

}
maxendinghere=maxsofar=b[0];
min1[0]=-b[0];
for(i=1;i<n;i++)
{
//maxendinghere=maxendinghere+b[i]>0?maxendinghere+b[i]:0;
maxendinghere=maxendinghere+b[i];
maxendinghere=maxendinghere>b[i]?maxendinghere:b[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
min1[i]=-maxsofar;
}
maxendinghere=maxsofar=b[n-1];
min2[n-1]=-b[n-1];
for(i=n-2;i>=0;i--)
{
//maxendinghere=maxendinghere+b[i]>0?maxendinghere+b[i]:0;
maxendinghere=maxendinghere+b[i];
maxendinghere=maxendinghere>b[i]?maxendinghere:b[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
min2[i]=-maxsofar;
}
long globalmax=0;
/*
for(i=0;i<n;i++)
{
System.out.println(a[i]+" "+b[i]+" "+min1[i]+" "+max1[i]+" "+min2[i]+" "+max2[i]);
}
*/
for(i=1;i<n;i++)
{
long m1=max1[i-1]-min2[i];
m1=Math.abs(m1);
long m2=max2[i]-min1[i-1];
m2=Math.abs(m2);
m1=m1>m2?m1:m2;
globalmax=globalmax>m1?globalmax:m1;
}
System.out.println(globalmax);
}

}

So abstract the list of ints to a list of three subsets.

list of numbers= {a, b, c} where a,b,c are sums of contiguous numbers in the array and a,b,c are contiguous.

Each of those subsets represents the sum of contiguous numbers in the array. We are looking for the highest and lowest. Note that it is impossible for A or C to have the same signage (positive or negative) as B. Also, if either A or C is the empty set, then the positive subset is the highest and the negative subset is the lowest. If both A and C are the empty set, then B is either the high subset or low subset based off of B's signage. Also lets specify that, B can never be an empty set unless both A and C are empty sets. Now the important thing to note here is that we are going to try to maximize the absolute value of B. This is important because it will allow us to take the highest absoulute value of either A or C and get the highest combined difference.

So let's take a look at some real numbers
n = {a, b, c}

int[] array = {100, -500, 2, -7, 50, -51, 3, -2, 4, 300, -150 };

so n = {100, -506, 305}

So here we can see we should grab the array that adds up to -506 (-500, 2, -7, 50, -51) and the array that adds up to 305 (3, -2, 4, 300).

So basically the algorithm is this
1) Pass through the array and calculate the sums
2) Figure out the largest absolute value the sub array B can be
3) Figure out if either A or C should be the other array


Here is some code that I wrote that does what I outlined above. It was written before I really understood why the codeworks so it could be prettied up, but I am too lazy to do so :)

// 2 -2 1 -1 3 12
            int[] array = {100, -500, 2, -7, 50, -51, 3, -2, 4, 300, -150 };
            int[] sumIndex = new int[array.Length];
            int sum = 0;
            int highEndIndex = 0;
            int lowEndIndex =0;
            int high = 0;
            int low = 0;

            for (int i = 0; i < array.Length; i++)
            {
                sum += array[i];
                sumIndex[i] = sum;
                if (sum > high)
                {
                    high = sum;
                    highEndIndex = i;
                }
                else if (sum < low)
                {
                    low = sum;
                    lowEndIndex = i;
                }
            }

            bool isLowFirst = Math.Abs(low) > highEndIndex;
            int startIndex = isLowFirst ? lowEndIndex : highEndIndex;
            int offset = isLowFirst ? low : high;

            for (int i = startIndex + 1; i < sumIndex.Length; i++)
            {
                if (i >= sumIndex.Length)
                    break;
                sumIndex[i] -= offset;
                if (!isLowFirst &&sumIndex[i] < low)
                {
                    low = sumIndex[i];
                    lowEndIndex = i;
                }
                else if (isLowFirst && sumIndex[i] > high)
                {
                    high = sumIndex[i];
                    highEndIndex = i;
                }
            }
                

            int highestInLow = low;
            int lowStartIndex = lowEndIndex;
            for (int i = lowEndIndex; i >= 0 || i >= highEndIndex; i--)
            {
                int sumToCompare = i == 0 ? 0 : sumIndex[i-1];
                if (sumToCompare> highestInLow)
                {
                    highestInLow = sumToCompare;
                    lowStartIndex = i;
                }
            }

            int lowestInHigh = high;
            int highStartIndex = highEndIndex;
            for (int i = highStartIndex; i >= 0 || i >= lowEndIndex; i--)
            {
                int sumToCompare = i == 0 ? 0 : sumIndex[i - 1];
                if (sumToCompare < lowestInHigh)
                {
                    lowestInHigh = sumToCompare;
                    highStartIndex = i;
                }
            }

My solution in C++ (based on the same idea as some other answers with O(n) running time) :

#include <algorithm>
#include <iostream>
#include <vector>

int computeMaxDiff(std::vector<int> L) {
    int maxLeftNeg[L.size()], maxRightNeg[L.size()], maxLeftPos[L.size()], maxRightPos[L.size()];
    int maxDiff = 0, j;
    int tmp;

    maxLeftNeg[0] = L[0] < 0 ? L[0] : 0;
    maxLeftPos[0] = L[0] > 0 ? L[0] : 0;
    maxRightNeg[L.size() - 1] = L[L.size() - 1] < 0 ? L[L.size() - 1] : 0;
    maxRightPos[L.size() - 1] = L[L.size() - 1] > 0 ? L[L.size() - 1] : 0;
    for (int i = 1; i < L.size(); ++i) {
        maxLeftNeg[i] = (maxLeftNeg[i - 1] + L[i] < 0) ? maxLeftNeg[i - 1] + L[i] : 0;
        maxLeftPos[i] = (maxLeftPos[i - 1] + L[i] > 0) ? maxLeftPos[i - 1] + L[i] : 0;
        j = L.size() - 1 - i;
        maxRightNeg[j] = (maxRightNeg[j + 1] + L[j] < 0) ? maxRightNeg[j + 1] + L[j] : 0;
        maxRightPos[j] = (maxRightPos[j + 1] + L[j] > 0) ? maxRightPos[j + 1] + L[j] : 0;
    }
    for (int i = 0; i < L.size() - 1; ++i) {
        tmp = (i < L.size() - 1) ? 
            std::max(maxLeftPos[i] - maxRightNeg[i + 1], maxRightPos[i + 1] - maxLeftNeg[i])
            : std::max(maxLeftPos[i], - maxLeftNeg[i]);
        maxDiff = std::max(tmp, maxDiff);
    }
    return maxDiff;
}

int main(int argc, char **argv) {
    int ar[] = {2, -1, -2, 1, -4, 2, 8};
    std::vector<int> vec(ar, ar + sizeof(ar) / sizeof(int));
    std::cout << computeMaxDiff(vec) << std::endl;
    return 0;
}

This solution in python is short, O(n), I hope this will help u.

oo=float('inf')

def find_max_sum(A):
    n=len(A)

    #to avoid check for final element in for cycle
    max_sum=[-oo for i in xrange(n+1)]
    tmp_max=-oo
    for i in range(n-1,-1,-1):
        tmp_max=max(A[i],A[i]+tmp_max)
        max_sum[i]=max(max_sum[i],tmp_max)
    return max_sum



def solve(A):
    
    right_max,left_max=find_max_sum(A),find_max_sum(A[::-1])
    print right_max
    negate=lambda x:-1*x
    invert= lambda x:map(negate,x)

    right_min,left_min=invert(find_max_sum(invert(A))),invert(find_max_sum(invert(A[::-1])))
    n=len(A)
    maxdiff=-oo
    for i in range(n):
        if i<n-1:maxdiff=max(maxdiff,abs(left_max[i]-right_min[i+1]),abs(left_min[i]-right_max[i+1]))
    return maxdiff

print solve([2,-1 ,-2, 1, -4, 2, 8])
print solve([-1,-2,-3])

Am I missing something ? It seems too simple to me :)

public static int bestSplit(int[] arr) {
		int generalSum = 0;
		for (int i : arr)
			generalSum += i;

		int runningSum = 0;
		int bestSplitVal = Math.abs(generalSum);
		for (int i = 0; i < arr.length; i++) {
			runningSum += arr[i];
			if (Math.abs(generalSum - runningSum) > bestSplitVal) {
				bestSplitVal = generalSum - runningSum;
			}
		}
		return bestSplitVal;
	}

Will the following solution work?

1. Find maxsubsequence sum M1 (using Kadane's algorithm)
2. Negate the whole array and find again maxSubsequenceSum M2
3. M1 + M2 should be the absolute max difference. [M1 and M2 must be appearing in disjoint contiguous subarrays, for if they overlap, M1 and -M2 cannot be maximum +ve and maximum -ve values respectively]. and we have a proof by contradiction below]

He is expecting O(n) time algorithm

1. Find the max continues sum
2. Find the continues min sum
3. return 1-2

public static int findMaxDiff(int[] a) {
	int maxsum = 0;
	int maxEndingHere = 0;

	boolean wholeArray = true;
	for (int i = 0; i < a.length; i++) {
		maxEndingHere = Math.max(maxEndingHere + a[i], 0);
			
		if (maxEndingHere == 0) wholeArray = false;
			
		maxsum = Math.max(maxsum, maxEndingHere);
	}
	if (wholeArray) return maxsum;
		
	int minsum = 0;
	int minEndingHere = 0;
	for (int i = 0; i < a.length; i++) {
		minEndingHere = Math.min(minEndingHere + a[i], 0);
		
		minsum = Math.min(minsum, minEndingHere);
	}
		
	return maxsum - minsum;
}

Running time is O(n).

What about this:
Must the two subarrays be adjacent? Yes, because the part "in between", unless it is 0, can contribute to either subarray, making it more optimal.

If so, then let's find a split point defining subarrays A[0,i] and A[i+1,n], such that the maximal subarrays (spanning together over whole A) give the optimal absolute difference of sums, that can be easily done O(n).

Now, here comes an interesting bit. You can prove that the optimal global solution are possibly trimmed subarrays found in the first step. In other words, you cannot find the global optimal solution by trimming subarrays, which do not optimize the first step criterion.

And so, without further ado, to find the optimum solution we have to possibly trim one or both of the subarrays, or "expanding" subarrays starting from one-element subarrays on the left hand side and right hand side of a split point found in the first step, and this is done in O(n).

So final time complexity O(n), space complexity O(1).

#include<stdio.h>
void main()
{
int a[]={2,-1,-2,1,-4,2,8},n=sizeof(a)/sizeof(int),max[n],min[n],max_max,min_min,i=0;
max[0]=min[0]=max_max=min_min=a[0];
for(i=1;i<n;i++)
{
max[i]=(max[i-1]+a[i])>a[i]?max[i-1]+a[i]:a[i];
max_max=max[i]>max_max?max[i]:max_max;
min[i]=(min[i-1]+a[i])<a[i]?min[i-1]+a[i]:a[i];
min_min=min[i]<min_min?min[i]:min_min;
}
printf("%d\n",max_max-min_min);
}
Is this ok? it will work in O(n). Are we supposed to identify the subsets also or need to print the difference only?

An O(n) solution by finding maximum subsequences using Kadane's algorithm

1. Find maxsubsequence sum M1
2. Negate the whole array and find again maxSubsequenceSum M2
3. M1 + M2 should be the absolute max difference. [M1 and M2 must be appearing in disjoint contiguous subarrays, for if they overlap, M1 and -M2 cannot be maximum +ve and maximum -ve values respectively. and we have a proof by contradiction above]
4. Separately handle degenerate cases such as 1) the maximum subsum being contained in the minimum subsum and 2) vice versa

Full working implementation in java is below. Provide Input to the program as:
4 -1 7
-4 1 -7
-9 -4 1 2 -5 -7 -8
9 4 -1 -2 5 7 8

import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxAbsoluteDiff {

	static ArrayList<Integer> numbers = new ArrayList<Integer>();	
	int pstart = 0, pend = 0, nstart = 0, nend = 0;
	int maxpsumgbl = 0, maxnsumgbl = 0, absDiff = 0;

	public void readInput() {
		Scanner scanner = new Scanner(System.in);
		scanner.useDelimiter(System.getProperty("line.separator"));
		Pattern delimiters = Pattern.compile(System
				.getProperty("line.separator") + "|\\s");
		scanner.useDelimiter(delimiters);
		int i;
		while (scanner.hasNextInt()) {
			i = scanner.nextInt();
			numbers.add(i);			
		}
	}

	public void Kadane() {

		int maxpsumrunning = 0, maxnsumrunning = 0;
		int j = 0;

		for (; j < numbers.size(); j++) {
			maxpsumrunning += numbers.get(j);
			maxnsumrunning += -numbers.get(j);

			if (maxpsumgbl < maxpsumrunning) {
				maxpsumgbl = maxpsumrunning;
				pend = j;
			}

			if (maxpsumrunning < 0) {
				maxpsumrunning = 0;
				if (j + 1 < numbers.size() && numbers.get(j + 1) > 0)
					pstart = j + 1;
			}

			if (maxnsumgbl < maxnsumrunning) {
				maxnsumgbl = maxnsumrunning;
				nend = j;
			}

			if (maxnsumrunning < 0) {
				maxnsumrunning = 0;
				if (j + 1 < numbers.size() && -numbers.get(j + 1) > 0)
					nstart = j + 1;
			}
		}

		if (nstart > pstart && nend < pend) {
			int subsum = 0;
			for (int k = pstart; k < nstart; k++) {
				subsum += numbers.get(k);
			}

			if ((maxpsumgbl + maxnsumgbl - subsum) > subsum) {
				maxpsumgbl = maxpsumgbl + maxnsumgbl - subsum;
			} else {
				maxpsumgbl = subsum;
			}

		} else if (pstart > nstart && pend < nend) {

			int subsum = 0;
			for (int k = nstart; k < pstart; k++) {
				subsum += -numbers.get(k);
			}

			if ((maxnsumgbl + maxpsumgbl - subsum) > subsum) {
				maxnsumgbl = maxnsumgbl + maxpsumgbl - subsum;
			} else {
				maxnsumgbl = subsum;
			}
		}
		absDiff = maxpsumgbl + maxnsumgbl;
	}

	public static void main(String[] args) {
		MaxAbsoluteDiff maxsss = new MaxAbsoluteDiff();
		maxsss.readInput();
		maxsss.Kadane();
		System.out.println("Max Abs Diff=" + maxsss.absDiff);

	}
}

main()
{

int a[7] = {2,-1, -2, 1, -4, 2, 8};
int max = a[0], trackMax = 0;
int min = a[0], trackMin = 0;    
for(int i=1;i<7;i++)
{       
        
        trackMax = trackMax + a[i]; 
        trackMin = trackMin + a[i]; 
        if(trackMax < 0) trackMax = trackMax - a[i];
        else trackMin = trackMin = trackMin - a[i];
        if(trackMax >= max) max = trackMax; 
        else if (trackMin <= min) min = trackMin; 
        cout << min << "    " <<max << endl;
}

cout << max-min;

The code for this problem is given below.You can consider the following approach:
a.Find maximum continuous sub-array sum using kadane's algorithm.
b.Similarly find minimum continuous sub-array sum using the same approach.
c.Find the difference between the maximum and minimum element.

#include <stdio.h>
#include <stdlib.h>
int maxSumArrayNegative(int arr[],int size)
{
    int max_so_far=arr[0],i;
    int max_ending_here=arr[0];
    for(i=1;i<size;i++)
    {
        max_ending_here=max_ending_here+arr[i];
        if(max_so_far<max_ending_here)
        {
            max_so_far=max_ending_here;
        }
    }
    return max_so_far;
}

int maxSumArrayPositive(int arr[],int size)
{
    int max_far=0,i;
    int max_ending=0;
    for(i=1;i<size;i++)
    {
        max_ending=max_ending+arr[i];
        if(max_ending<0)
        {
            max_ending=0;
        }
        if(max_far<max_ending)
        {
            max_far=max_ending;
        }
    }
    return max_far;
}

int minSumArray(int arr[],int size)
{
    int min_so_far=arr[0];
    int min_ending_here=arr[0],i;
    for(i=1;i<size;i++)
    {
        min_ending_here=min_ending_here+arr[i];
        if(min_so_far>min_ending_here)
        {
            min_so_far=min_ending_here;
        }
    }
    return min_so_far;
}
int main()
{
    int arr[3]={-1,-2,-5};
    int n=sizeof(arr)/sizeof(arr[0]);
    int i,size=0,diff;
    for(i=0;i<n;i++)
    {
        if(arr[i]<0)
            size++;
    }
    if(size==n)
    {
        int max=maxSumArrayNegative(arr,n);
        int min=minSumArray(arr,n);
        diff=max-min;

    }
    else
    {
        int max=maxSumArrayPositive(arr,n);
        int min=minSumArray(arr,n);
        diff=max-min;
    }
    printf("The diff is %d ",diff);
}

So this is what I got, there are no error checking which is obviously bad but I assume we are all coding and making suggestions for valid entries primarily so keep that in mind:

public int FindMaxDiff(int[] input, int[] max, int[] min)
{
  int maxIndex=0, minIndex=0, leftIndex=0,rightIndex=input.length()-1, midMaxIndex=0, midMinIndex=0, largestSum, smallestSum;
  bool isMaxRight;
  int[] subArray;
  
  //Find The Min and Max values for the array
  //Note that multiple Min and Max values may 
  //move the index but doesnt change the outcome
  for(int probe = 0; probe < input.length()-1; probe++) 
  {
    if(input[maxIndex] < input[probe]) maxIndex = probe;
    if(input[minIndex] > input[probe]) minIndex = probe;
  }


  //Determine if the max value is on the left or right of the minimum value
  if(maxIndex > minIndex)
  {
    isMaxRight = true;
  } else
  {
    isMaxRight = false;
  }

  if(isMaxRight)
  {
    //Determine the rightmost index for the max sub array
    for(int end = rightIndex; end > maxIndex; end -= 1)
    {
      subArray = arraycopy(input,maxIndex,end);
      int newSum = ArraySum(subArray);
      if(largestSum == null)
      {
        largestSum = newSum;
      }
      else
      {
        if(largestSum < newSum)
        {
           largestSum = newSum;
           rightIndex = end;
        }
      }
    }

    //Determine the leftmost index for the min sub array
    for(int start = 0; start < minIndex; start += 1)
    {
      subArray = arraycopy(input,start,minIndex);
      int newSum = ArraySum(subArray);
      if(smallestSum == null)
      {
        smallestSum = newSum;
      }
      else
      {
        if(smallestSum > newSum)
        {
           smallestSum = newSum;
           leftIndex = start;
        }
      }
    }
  }
  else
  {
    //Determine the rightmost index for the max sub array
    for(int end = rightIndex; end > minIndex; end -= 1)
    {
      subArray = arraycopy(input,minIndex,end);
      int newSum = ArraySum(subArray);
      if(smallestSum == null)
      {
        smallestSum = newSum;
      }
      else
      {
        if(smallestSum > newSum)
        {
           smallestSum = newSum;
           rightIndex = end;
        }
      }
    }

    //Determine the leftmost index for the min sub array
    for(int start = 0; start < maxIndex; start += 1)
    {
      subArray = arraycopy(input,start,maxIndex);
      int newSum = ArraySum(subArray);
      if(largestSum == null)
      {
        largestSum = newSum;
      }
      else
      {
        if(largestSum < newSum)
        {
           largestSum = newSum;
           leftIndex = start;
        }
      }
    }
  }

  //The subArray between the max & min will go to the 
  //side that it benefits or max if its mutual benefitting
  if(isMaxRight)
  {
    int[] middle = arraycopy(input, minIndex+1, maxIndex-1);
  } else
  {
    int[] middle = arraycopy(input, maxIndex+1, minIndex-1);
  }
  int midSum = ArraySum(middle);
  
  // The Solution
  if(midSum >= 0)
  {
    if(isMaxRight)
    {
      max = arraycopy(input, minIndex+1,rightIndex);
      min = arraycopy(input, leftIndex, minIndex);
    }
    else
    {
      max = arraycopy(input, leftIndex,minIndex-1);
      min = arraycopy(input, minIndex, rightIndex);
    }
    return Math.abs((largestSum + midSum) - smallestSum);
  } 
  else
  {
    if(isMaxRight)
    {
      max = arraycopy(input, maxIndex,rightIndex);
      min = arraycopy(input, leftIndex, maxIndex-1);
    }
    else
    {
      max = arraycopy(input, leftIndex,maxIndex);
      min = arraycopy(input, maxIndex+1, rightIndex);
    }
    return Math.abs(largestSum - (midSum + smallestSum));
  }
}

O(n) solution can be found at
sites.google.com/site/spaceofjameschen/home/array/find-two-disjoint-contiguous-sub-arrays-such-that-the-absolute-difference

While thinking over this problem I just realized that maximum and minimum subarrays can overlap in only two scenarios:
1) When sum of the common numbers is zero. If sum of common sequence would have been +ve then it would have been part of maximum subarray and not of minimum subarray. Vice verse for -ve sum for common subarray.
2) One subarray is part of other. For example 10, 9, -1, -2, 10 10

Based on the above two possiblilities
1) Find maximum subarray
2) Find minimum subarray
3) If common subarray is zero then it can go either on maximum or minimum side.
4) If one subarray is part of other then find left and right part (non overlapping) of larger subarray and find the difference between this larger part and common elements.

Hence the complexity of this algo is same as finding maximum/minimum subarray problem.

#include <algorithm>
using namespace std;
int computMaxDiff(int *array,int len)
{
int *maxarray=new int[len];
int *minarray=new int[len];
maxarray[0]=array[0];
minarray[0]=-array[0];
int currentmax=maxarray[0]>0?array[0]:0;
int currentmin=minarray[0]>0?minarray[0]:0;
for(int i=1;i<len;i++)
{
currentmax+=array[i]; //max
maxarray[i]=max(currentmax,maxarray[i-1]);
if(currentmax<0) currentmax=0;

currentmin+=-array[i]; // max of -array
minarray[i]=max(currentmin,minarray[i-1]);
if(currentmin<0) currentmin=0;
}

for (int i=0;i<len;i++) //min of array
minarray[i]=-minarray[i];


int *revmaxarray=new int[len];
int *revminarray=new int[len];
revmaxarray[len-1]=array[len-1];
revminarray[len-1]=-array[len-1];
int revcurrentmax=revmaxarray[len-1]>0?revmaxarray[len-1]:0;
int revcurrentmin=revminarray[len-1]>0?revminarray[len-1]:0;
for(int i=len-2;i>=0;i--)
{
revcurrentmax+=array[i];
revmaxarray[i]=max(revcurrentmax,revmaxarray[i+1]);
if(revcurrentmax<0) revcurrentmax=0;

revcurrentmin+=-array[i];
revminarray[i]=max(revcurrentmin,revminarray[i+1]);
if(revcurrentmin<0) revcurrentmin=0;
}

for (int i=0;i<len;i++)
revminarray[i]=-revminarray[i];

int maxdiff=0;
for (int i=0;i<len;i++)
{
int currMax=max(abs(maxarray[i]-revminarray[i]),abs(minarray[i]-revmaxarray[i]));
if(currMax>maxdiff)
maxdiff=currMax;
}

return maxdiff;
}
int _tmain(int argc, _TCHAR* argv[])
{
int array[5]={-3,4,-1,4,5};
int maxdiff=computMaxDiff(array,5);
return 0;
}

step 1 : find the sum of whole array. assign it TotalSum O(n)
step 2 : Lets have a few variables SumFromBegining=0, SumFromEnd=TotalSum, MaxDifference=0, MaxDifferenceSplitIndex=0. all these are integers or long ---O(1)
step 3 : Iterate through the array from beginning to end.
for each iteration you need need to do the following
1. add the current array element ie. array[i] to SumFromBegining
2. subtract the current array element ie. array[i] from SumFromEnd
3. Difference=absolute(SumFromEnd-SumFromBegining)
4. if Difference > MaxDifference then MaxDifference=Difference and MaxDifferenceSplitIndex=i

now this process is of O(n)

After the iteration array[0 to MaxDifferenceSplitIndex ] and array[MaxDifferenceSplitIndex+1 to n] are the answer.

this is a solution with O(n)

hope i did not make a mistake..:-)

I've been through all of these solutions and correct me if i'm wrong, but i think absolutely none of them work for all possible cases. There's one or two which work, but they aint 0(n).

for this problem finding maximum and minimum contiguous don't work. for example consider this two test case:
1)array=[-6, 3, 5, 4, -1, -7, 17, 8]
in this case maxSum=25 and minSum=-8 if we search disjoint contiguous subarray. so the absolute difference is equal 33. however, the max difference is 35 if we separate [-6] and [3, 5, 4, -1, -7, 17, 8]. sum1=-6, sum2=29 so difference is 35.
2)array=[4, -1, 5]
the same above maximum absolute difference between two disjoint contiguous subarray is 6.[-1] and [5].

1. Given an array, find the following max/min continuous array:
- left_min_array: continuous max array
- left_max_array: continuous min array
- right_min_array: reverse the array, calculate the continuous max array, reversed again
- right_max_array: reverse the array, calculate the continuous min array, reversed again
2. Iterate the array, find the maximum among the following four integers:
- abs(left_min_array[i]) + abs(right_min_array[i+1])
- abs(left_min_array[i]) + abs(right_max_array[i+1])
- abs(left_max_array[i]) + abs(right_min_array[i+1])
- abs(left_max_array[i]) + abs(right_max_array[i+1])
And store the largest result in an array, let's call result
3. The maximum difference is the max element in the result array

Code is attached at the end, following are the test cases:
- {2,-1,-2,12,453,-9,2,8}
- {7,-1,4}
- {1,2,3,4,5}
- {-1,-3,-5,-2,-1,-4}

public static int[] findMaxOrMin(int[] array,boolean findMax) {
    int[] res = new int[array.length];

    res[0] = array[0];
    for(int i=1;i<array.length;i++) {
      if(findMax)
        res[i] = Math.max(res[i-1]+array[i],array[i]);
      else
        res[i] = Math.min(res[i-1]+array[i],array[i]);
    }

    return res;
  }

  public static int[] reverseArray(int[] array) {

    for(int i=0;i<array.length/2;i++) {
      int temp = array[(array.length-1)-i];
      array[(array.length-1)-i] = array[i];
      array[i] = temp;
    }
    return array;
  }

  public static int findMaxDiff(int[] array) {

    int[] left_min_array = findMaxOrMin(array,false);
    int[] left_max_array = findMaxOrMin(array,true);
    int[] right_min_array = reverseArray(findMaxOrMin(reverseArray(Arrays.copyOfRange(array,0,array.length)),false));
    int[] right_max_array = reverseArray(findMaxOrMin(reverseArray(Arrays.copyOfRange(array,0,array.length)),true));

    int[] result = new int[array.length-1];
    int largestIndex = 0;

    for(int i=0;i<result.length;i++) {
      int combo1 = Math.abs(left_min_array[i])+Math.abs(right_min_array[i+1]);
      int combo2 = Math.abs(left_min_array[i])+Math.abs(right_max_array[i+1]);
      int combo3 = Math.abs(left_max_array[i])+Math.abs(right_min_array[i+1]);
      int combo4 = Math.abs(left_max_array[i])+Math.abs(right_max_array[i+1]);
      result[i] = Math.max(Math.max(Math.max(combo1,combo2),combo3),combo4);
      if(i>1)
        largestIndex = result[i]>result[i-1] ? i:largestIndex;
    }
    return result[largestIndex];
  }

step 1 : find the sum of whole array. assign it TotalSum O(n)
step 2 : Lets have a few variables SumFromBegining=0, SumFromEnd=TotalSum, MaxDifference=0, MaxDifferenceSplitIndex=0. all these are integers or long ---O(1)
step 3 : Iterate through the array from beginning to end.
for each iteration you need need to do the following
1. add the current array element ie. array[i] to SumFromBegining
2. subtract the current array element ie. array[i] from SumFromEnd
3. Difference=absolute(SumFromEnd-SumFromBegining)
4. if Difference > MaxDifference then MaxDifference=Difference and MaxDifferenceSplitIndex=i

now this process is of O(n)

After the iteration array[0 to MaxDifferenceSplitIndex ] and array[MaxDifferenceSplitIndex+1 to n] are the answer.

this is a solution with O(n)

here's a O(n) solution:

// {1, 2, -5, 10, 0, - 15, -1, 3, -4}
// maximize 10 - (-17)) = 27

// let's consider a pointer that moves through the set which breaks set into two
// regions - left and right which are subsets

// for each of these subsets we want to consider max and min values
// and then use the ones that give best possible diff

// following structure keeps track of max and min for a given subset
struct elem {
	int maxsum;
	int minsum;
	int min;
	int max;

	elem() : maxsum(0), minsum(0), min(0), max(0) {}
	elem& operator = (int a) { maxsum = a; minsum = a; min = a; max = a; return *this; }
	elem& operator + (int a) { maxsum+=a; if (maxsum < 0) maxsum = 0; if (maxsum > max) max = maxsum;
	                           minsum+=a; if (minsum > 0) minsum = 0; if(minsum < min) min = minsum; return *this; }
};

int maxdiffinsubsets(int A[], int size)
{
	elem *DA1 = new elem [size - 1];
	elem* DA2 = new elem [size - 1];
	int i;
	int bestdiff = 0;

	// create a dynamic array that stores min and max of all possible subsets
	DA1[0] = A[0];
	for (i = 1; i < size - 1; i++)
	{
		DA1[i] = DA1[i-1] + A[i]; 
	}

	// this second array is the counter part to the first one so for example
	// for a set {1, 2, -1 } if DA1 got {1} covered, DA2 will cover {2, -1}

	DA2[size-1] = A[size-1];
	for (i = size - 2; i >= 0; i--)
	{
		DA2[i] = DA2[i + 1] + A[i];
	}

	// find the best combination
	for (i = 0; i < size - 1; i++)
	{
		int temp = max(DA1[i].max - DA2[i].min, DA2[i].max - DA1[i].min);
		if (temp > bestdiff)
			bestdiff = temp;
	}

	return bestdiff;
}

int main (int argc, void** argv)
{
	int A[] = {4,-1,7}; //{1, 2, 5, -15,5,-2, 1, 0};//{1, 2, -5, 10, 0, - 15, -1, 3, -4};
	int size = sizeof(A)/sizeof(int);

	cout<<maxdiffinsubsets(A, size)<<endl;
	_getch();

}

Can anybody comment on my approach .
1. find the max sum subsequence using DP. Store the sum and store the subsequence. Replace those elements by INT_MAX.
2. find the min sum subsequence using DP. store the sum and subsequence
3. Now calculate the difference, and print those sets.
I think there is no way this subsets will overlap.

This is O(n) solution since steps 2 and 3 takes O(n) in DP.

int get_index(vector<int>& a)
{
    int n = a.size();
    if (n <=1 ) return -1;
    vector<long long int> prefix_sum(n, 0);
    prefix_sum[0] = a[0];
    for (int i=1; i < n; i++) prefix_sum[i] += prefix_sum[i-1];
    long long int min_diff min_idx(-1);
    for (int i=0; i < n-1; i++)
    {
           long long  int diff = abs( prefix_sum[i] - prefix_sum[n-1] + prefix_sum[i+1] );
           if (min_idx == -1 || diff < min_diff) { min_diff = diff; min_idx = i; } 
    }
    return min_idx ; 
}

List<int> maxArray = new List<int>();
            List<int> minArray = new List<int>();
            List<int> currentRun = new List<int>();

            int currentRunCount = 0;
            int max = 0;
            int min = 0;
            for (int i = 0; i < array.Length; i++)
            {
                currentRun.Add(i);
                currentRunCount += array[i];

                if (currentRunCount > 0)
                {
                    if (currentRunCount >= max)
                    {
                        if (maxArray.Count == 0 || maxArray.ElementAt(maxArray.Count - 1) == currentRun.ElementAt(0) - 1)
                        {
                            maxArray.AddRange(currentRun);
                        }
                        else
                        {
                            maxArray = currentRun;
                        }

                        max = currentRunCount;
                        currentRunCount = 0;
                        currentRun = new List<int>();
                    }
                }
                 
                if (currentRunCount < 0)
                {
                    if (currentRunCount <= min)
                    {
                        if (minArray.Count == 0 || minArray.ElementAt(minArray.Count - 1) == currentRun.ElementAt(0) - 1)
                        {
                            minArray.AddRange(currentRun);
                        }
                        else
                        {
                            minArray = currentRun;
                        }

                        min = currentRunCount;
                        currentRunCount = 0;
                        currentRun = new List<int>();
                    }
                }

}

I came across this problem and thought about this and came up with the possible solution. I am unable to find cases in order to fail this solution. Can someone please enumerate a set for the same?

My algorithm:

1.Calculate the continuous sum of all elements while going from 1 to n and store them in an array . Do the same while going from n to 1
2. In the first array mark a point which has minimum value and which has maximum value
. Do the same for the second array
3. Check for four scenarios.
a) Break array just after array 1 has hit a minimum value
b) Break array just before array 1 has hit a max value
c) Break array just before array 2 has hit a minimum value
d) Break array just after array 2 has hit a max value
4. Max of (a,b,c,d) from above is the answer

Example:
Array : 10,1,3,-10,2

Array 1: 10,11,14,4,6 Max: 14 Min: 4
Array 2: 6,-4,-5,-8,2 Max: 6 Min: -8
a) Break after Min:4 i.e Break after -10 in Array . Absolute Diff is 2
b) Break before Max:14 i.e Break before 3 in Array . Absolute Diff is 16
c) Break after Max:6 i.e Break after 10 in Array . Absolute Diff is 14
d) Break before Min: -8 i.e Break before -10 in Array . Absolute diff is 22

Max(a,b,c,d) = 22

Solution complexity is O(n)

I came across this problem and thought about this and came up with the possible solution. I am unable to find cases in order to fail this solution. Can someone please enumerate a set for the same?

My algorithm:

1.Calculate the continuous sum of all elements while going from 1 to n and store them in an array . Do the same while going from n to 1
2. In the first array mark a point which has minimum value and which has maximum value
. Do the same for the second array
3. Check for four scenarios.
a) Break array just after array 1 has hit a minimum value
b) Break array just before array 1 has hit a max value
c) Break array just before array 2 has hit a minimum value
d) Break array just after array 2 has hit a max value
4. Max of (a,b,c,d) from above is the answer

Example:
Array : 10,1,3,-10,2

Array 1: 10,11,14,4,6 Max: 14 Min: 4
Array 2: 6,-4,-5,-8,2 Max: 6 Min: -8
a) Break after Min:4 i.e Break after -10 in Array . Absolute Diff is 2
b) Break before Max:14 i.e Break before 3 in Array . Absolute Diff is 16
c) Break after Max:6 i.e Break after 10 in Array . Absolute Diff is 14
d) Break before Min: -8 i.e Break before -10 in Array . Absolute diff is 22

Max(a,b,c,d) = 22

Solution complexity is O(n)

I think Loler is right, the algorithm could be implemented in O(n), and here is my code:

#include <iostream>
#include <vector>

void max_sum_diff( int a[], int n ) // time Complexity: O(n)
{
	std::vector<int> pmax(n,0), //max contiguous sum end with a[i]
		pmin(n,0), //min contiguous sum end with a[i]
		smax(n,0), //max contiguous sum begin with a[i]
		smin(n,0); //min contiguous sum begin with a[i]

	int sum = a[0];
	pmax[0] = pmin[0] = a[0];
	for( int i = 1; i <= n-1; ++i )
	{
		pmax[i] = std::max( pmax[i-1] + a[i], a[i] );
		pmin[i] = std::min( pmin[i-1] + a[i], a[i] );
		sum += a[i];
	}

	smax[n-1] = smin[n-1] = a[n-1];
	for( int i = n-2; i >=0; --i )
	{
		smax[i] = std::max( smax[i+1] + a[i], a[i] );
		smin[i] = std::min( smin[i+1] + a[i], a[i] );
	}

	//change pmax has the max sum in range[0,i], smax has the max sum in range[i,n-1]
	//so is pmin and smin
	for( int i = 1; i <= n-1; ++i )
	{
		pmax[i] = std::max( pmax[i-1], pmax[i] );
		pmin[i] = std::min( pmin[i-1], pmin[i] );
	}

	for( int i = n-2; i >= 0; --i )
	{
		smax[i] = std::max( smax[i+1], smax[i] );
		smin[i] = std::min( smin[i+1], smin[i] );
	}

	int diff1, diff2, max_diff = abs(sum);
	for( int i = 0; i <= n - 2; ++i )
	{
		diff1 = abs( pmax[i] - smin[i+1] );
		diff2 = abs( pmin[i] - smax[i+1] );
		max_diff = std::max( diff1, max_diff );
		max_diff = std::max( diff2, max_diff );
	}

	std::cout << "Max Diff: " << max_diff << std::endl;
}

int main( int argc, char* argv[] )
{
	int a[] = { 2, -1, -2, 1, -4, 2, 8 };
	max_sum_diff( a, 7 );

	return 0;
}

sites.google.com/site/spaceofjameschen/home/array/find-two-disjoint-contiguous-sub-arrays-such-that-the-absolute-difference

i am assuming the minimum sum of a sub array is negative or empty.
and that the maximum sum of a sub array is positive or empty.
the problem can be defined as follow:
1. Find the max sub sum
2. Find the min sub sum

if they do not intersect return their difference; otherwise check if the min sub sum is starting after the max sub sum:

[maxSubSumStart ---------- minSubSumStart ----------------MinSubSumEnd--------maxSubSumEnd]

I want to prove that if intersection is not allowed then either the left max sub sum or the right sub sum is the largest sub sum.
In this case each side of minSubSumArray is larger than the absolute value of minSubSumArray (otherwise their sum is below 0 and we would have taken only one part).
assume the left sub array is the bigger one.
That implies that it is also the biggest sub array in the array (because any other max sub array that wasn't added to the current max array, wasn't added because it is smaller (absolute value)than some minimum sub array, and therefore it is smaller then the minimum sub array and therefor smaller then the left and right parts of the maxsub array.

Therefore the result would be: max sub is the left side of the max array, and the min sub is the minimum sub array.

the same logic is true also in case the max array start in the middle of the min array

this is the code , i still need to do some re-factoring and also I might have some indexing issues:

static void PrintMaxDifferanceArray(int[] arr)
        {
            int max = 0;
            int tempMax = 0;
            int tempMaxStart =0;
            int maxStart =0;
            int maxEnd =0;

            int min = 0;
            int tempMin = 0;
            int tempMinStart = 0;
            int minStart = 0;
            int minEnd = 0;


            for (int i = 0; i < arr.Length; i++ )
            {
                if (tempMin + arr[i] > 0)
                {
                    tempMin = 0;
                    tempMinStart = i + 1;
                }
                else
                {
                    tempMin += arr[i];
                }

                if (tempMin < min)
                {
                    min = tempMin;
                    minStart = tempMinStart;
                    minEnd = i;
                }
                if (tempMax + arr[i] < 0)
                {
                    tempMax = 0;
                    tempMaxStart = i + 1;
                }
                else
                {
                    tempMax += arr[i];
                }


                if (tempMax > max)
                {
                    max = tempMax;
                    maxStart = tempMaxStart;
                    maxEnd = i;
                }
            }
            //The maximum sub array starts in the middle of the min sub array.
            //minStart------------maxStart-----------------minEnd
            if (maxStart >= minStart && maxStart <= minEnd)
            {
                int leftSum =0;
                //take the left part of the min array. from min start to max start
                arr.ToList().Skip(minStart).Take(maxStart - minStart).ToList().ForEach(x => leftSum += x);


                //take the right part of the min array. from max end to min end
                int rightSum = 0;
                if(maxEnd<minEnd)
                    arr.ToList().Skip(maxEnd + 1).Take(minEnd - maxEnd).ToList().ForEach(x => rightSum += x);

                
                if (leftSum < rightSum)
                {
                    Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}",minStart,maxStart-1,maxStart,maxEnd);
                    Console.WriteLine("the difference is {0}", max-leftSum);
                }
                else
                {
                    Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", maxEnd+1, minEnd, maxStart, maxEnd);
                    Console.WriteLine("the difference is {0}", max - rightSum);
                }
                return;
            }
            //The minimum sub array starts in the middle of the max sub array.
            //maxStart------------minStart-----------------maxEnd
            if (minStart >= maxStart && minStart <= maxEnd)
            {
                int leftSum = 0;
                //take the left part of the max array. from max start to min start
                //maxStart------------minStart
                arr.ToList().Skip(maxStart).Take(minStart - maxStart).ToList().ForEach(x => leftSum += x);


                //take the right part of the max array. from min end to max end
                int rightSum = 0;
                //minEnd+1------------maxEnd
                if (minEnd < maxEnd)
                    arr.ToList().Skip(minEnd + 1).Take(maxEnd - minEnd).ToList().ForEach(x => rightSum += x);
                if (leftSum > rightSum)
                {
                    Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", maxStart, minStart - 1, minStart, minEnd);
                    Console.WriteLine("the difference is {0}", leftSum-min);
                }
                else
                {
                    Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", minStart, minEnd, minEnd+1, maxEnd);
                    Console.WriteLine("the difference is {0}", rightSum - min);
                }
                return;
            }

            //no intersection
            Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", minStart, minEnd, maxStart, maxEnd);
            Console.WriteLine("the difference is {0}", max - min);
            


        }

1. Find the cumulative sum for 0<=i<n and store sum in cumulative[ ]
2. Find j, such that abs(cumulative[ j ] - cumulative [n-1]) is maximum
3. 0 to j is one subarray and j+1 to n-1 is the other subarray

This solution should work for cases:
1 - compute kadane as follow: var kadane = function (arr, k, j, isMin)
which should return min/max sum (according to isMin flag) for the arr elements starting at k index and end (inclusive) at j index.
return value should be an object that includes the sum, start index, end index.
2 - find max when k==0 and j==arr.length-1. let's call it MAX and assume it has startIndex==si and endIndex==ei;
3 - find min when k==0 and j==arr.length-1. let's call it MIN and assume it has startIndex==si and endIndex==ei;
4 - for the output of 2 MAX - find min on the right side of it using k==MIN.endIndex+1 and j==arr.length and on the left side of it using k==0 and j==MIN.startIndex-1 (if possible and out of arr indexes).
5 - do the as in 4 step for the MIN (find max on both sides of it).
6 - out of the result in 4 and 5 take the highest and lowest among the two and calculate the range of them with MAX and MIN respectively.
7 - among the two pairs from step 6 - MIN and a max on its left/right and MAX and a min on its left/right choose the pair with the higher range and return it.

var Range = function (s, e, sum, isMin) {
	this.sum = sum;
	this.s = s;
	this.e = e;
	this.isMin = isMin;
};

var kadane = function (arr, k, j, isMin) {
	var mSoFar = arr[k];
	var mEndHere = arr[k];
	var s = k;
	var e = k;
	var st = k;
	var i = k+1;
	var cur;
	
	for(; i < j+1; i++){
		cur = arr[i];
		if((isMin && (mEndHere > 0)) || (!isMin && (mEndHere < 0))) {
			mEndHere = cur;
			st = i;
		}
		else{
			mEndHere += cur;
		}
		
		if((isMin && (mEndHere < mSoFar)) || (!isMin && (mEndHere > mSoFar))){
			mSoFar = mEndHere;
			e = i;
			s = st;
		}
	}
	
	return new Range (s, e, mSoFar, isMin);
	
};

If there are 2 elements in the array, or all the elements are zero, the
solution is really trivial. If there are less than 2 elements, there is no
solution.

If all the numbers are non-negative, the problem is completely different from
if you have both signs, all positive is somewhat easier. The smaller sub-array
will contain only 1 element, and the larger subarray will contain either the
front or the back. Start with the front of the array being the 'large' value
and the second item being 'small', we store this as our 'current optimum'. Now
add the 2nd item to 'large' and call the next element 'small'; if this is
better than our first solution, we store it as our current optimum. We go
through the array forwards the whole way through, then we do the same thing
going backwards. The optimal solution we find after both passes is the optimal
solution. This solves in order n (3 passes through n elements). The same logic
works if all the elements are 0 or negative.

If we have both positive and negative numbers, create a 2nd array (partioned
array) 'partitioning' every positive and negative sequence: 2 -1 -2 1 -4 2 8
becomes [2] [-3] [1] [-4] [10]. I am pretty sure this is the right direction,
but from here on out, I bet someone (possibly me with more time) comes up with
something better than I have following.


Now create yet another array combining all the negative elements if and only if
their sum is less than the number between them. Repeat this process until you
cannot. So you get [-6] in this example. Now create yet another array doing
this with the positive values, giving you [2][1][10]. The largest of the
positive and smallest negative are the solution if we can ignore the
requirement the arrays do not overlap, and the solution if they do not overlap.
So far, we've done nothing beyond order n. If they overlap, we can find a
place to split the segment that overlaps fairly easily, and this is almost
always the correct solution, but you can come up with examples where it is not.
I think going back to our partioned array and finding other combinations is the
trick, but cannot think of better than n^2 way to do that.


Of course, you need to store a bit more to go back and find the array indexes,
but that is trivial so I left it out.

Based upon comments above, I have written following code.

{
public class DisjointSubarraysLinearTime {
public static void main(String[] args) {
int[] input = {2, -1, -2, 1, -4, 2, 8};
System.out.println("diff: " + getDifference(input));
}
public static int getDifference(int[] a) {
int[] MAX = new int[a.length];
int[] MIN = new int[a.length];
int result = Integer.MIN_VALUE;
setMinMaxArrays(a, MIN, MAX);
for (int i = 0; i < a.length-1; i++) {
result = Math.max(result, Math.abs(MAX[i] - MIN[i+1]));
}
for (int i = 0; i < a.length; i++) {
a[i] = -a[i];
}
setMinMaxArrays(a, MIN, MAX);
for (int i = 0; i < a.length-1; i++) {
result = Math.max(result, Math.abs(MAX[i] - MIN[i+1]));
}
return result;
}
public static void setMinMaxArrays(int[] a, int[] MIN, int[] MAX) {
MAX[0] = a[0];
int maxEndingHere = a[0];
for (int i = 1; i < a.length; i++) {
if (maxEndingHere < 0) {
maxEndingHere = a[i];
}
else {
maxEndingHere += a[i];
}
MAX[i] = Math.max(maxEndingHere, MAX[i-1]);
}
MIN[a.length-1] = a[a.length-1];
int minEndingHere = a[a.length-1];
for (int i = a.length - 2; i >= 0; i--) {
if (minEndingHere > 0) {
minEndingHere = a[i];
}
else {
minEndingHere += a[i];
}
MIN[i] = Math.min(minEndingHere, MIN[i+1]);
}
}
}
}

Based upon comments above, I have written following code(formatted):

public class DisjointSubarraysLinearTime {
	public static void main(String[] args) {
		int[] input = {2, -1, -2, 1, -4, 2, 8};
		System.out.println("diff: " + getDifference(input));
	}
	public static int getDifference(int[] a) {
		int[] MAX = new int[a.length];
		int[] MIN = new int[a.length];
		int result = Integer.MIN_VALUE;
		setMinMaxArrays(a, MIN, MAX);
		for (int i = 0; i < a.length-1; i++) {
			result = Math.max(result,  Math.abs(MAX[i] - MIN[i+1]));
		}
		for (int i = 0; i < a.length; i++) {
			a[i] = -a[i];
		}
		setMinMaxArrays(a, MIN, MAX);
		for (int i = 0; i < a.length-1; i++) {
			result = Math.max(result,  Math.abs(MAX[i] - MIN[i+1]));
		}
		return result;
	}
	public static void setMinMaxArrays(int[] a, int[] MIN, int[] MAX) {
		MAX[0] = a[0];
		int maxEndingHere = a[0];
		for (int i = 1; i < a.length; i++) {
			if (maxEndingHere < 0) {
				maxEndingHere = a[i];
			}
			else {
				maxEndingHere += a[i];
			}
			MAX[i] = Math.max(maxEndingHere, MAX[i-1]);
		}
		MIN[a.length-1] = a[a.length-1];
		int minEndingHere = a[a.length-1];
		for (int i = a.length - 2; i >= 0; i--) {
			if (minEndingHere > 0) {
				minEndingHere = a[i];
			}
			else {
				minEndingHere += a[i];
			}
			MIN[i] = Math.min(minEndingHere, MIN[i+1]);
		}
	}
}

I won't prove it, but it's true that you can find the max or min subsequence of an array in O(n) time and space.

Assuming that's true, compute the max and min subarrays. If they don't overlap, then you have your answer.

What if they do overlap?

If they overlap in the middle (e.g. [1, 5], [3, 10] overlap at [3, 5]), observe that if we remove the overlapping part from both (max and min) subarrays, that that will not change the absolute value of the difference of their sums.

WLOG, assume the min sequence contains the max sequence. Then, our disjoint max sequence will be *the* max sequence, and our disjoint min sequence will be either the left or right part that borders the inner max--return the side with smaller (more negative) sum.

It's a bit more involved to prove that the smaller side of the containing subsequence will still be the right one, but if you try and fail to find a counterexample, you'll see why.

#define maxn 100000

int l[maxn];
int r[maxn];

int work(vector<int> a) {
    int n = a.size();
    l[0] = a[0];
    for (int i=1;i<n;i++)
        l[i] = max(a[i],l[i-1]+a[i]);
    for (int i=1;i<n;i++)
        l[i] = max(l[i-1],l[i]);
    r[n-1] = a[n-1];
    for (int i=n-2;i>-1;i--)
        r[i] = min(a[i],r[i+1]+a[i]);
    for (int i=n-2;i>-1;i--)
        r[i] = min(r[i],r[i+1]);
    int ans = 0;
    for (int i=0;i<n-1;i++)
        ans = max(ans,l[i]-r[i+1]);
    return ans;
}

int maxdifference(vector<int> a) {
    int ans = 0;
    ans = max(ans,work(a));
    for (int i=0;i<a.size();i++) a[i] = -a[i];
    ans = max(ans,work(a));
    return ans;
}

This solution in python is short, O(n), I hope this will help u.

oo=float('inf')

def find_max_sum(A):
    n=len(A)

    #to avoid check for final element in for cycle
    max_sum=[-oo for i in xrange(n+1)]
    tmp_max=-oo
    for i in range(n-1,-1,-1):
        tmp_max=max(A[i],A[i]+tmp_max)
        max_sum[i]=max(max_sum[i],tmp_max)
    return max_sum



def solve(A):
    
    right_max,left_max=find_max_sum(A),find_max_sum(A[::-1])
    print right_max
    negate=lambda x:-1*x
    invert= lambda x:map(negate,x)

    right_min,left_min=invert(find_max_sum(invert(A))),invert(find_max_sum(invert(A[::-1])))
    n=len(A)
    maxdiff=-oo
    for i in range(n):
        if i<n-1:maxdiff=max(maxdiff,abs(left_max[i]-right_min[i+1]),abs(left_min[i]-right_max[i+1]))
    return maxdiff

print solve([2,-1 ,-2, 1, -4, 2, 8])
print solve([-1,-2,-3])

int main()
{
	
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int n,i,j;
	int dp1[20][2],dp2[20][2],a[20];
	//memset(dp1,0,sizeof(dp1));
	cin>>n;
	for(i=0;i<n;i++){cin>>a[i];}
	dp1[0][0]=a[0];
	dp1[0][1]=a[0];
	for(i=1;i<n;i++)
	{
		dp1[i][0]=min(a[i],a[i]+dp1[i-1][0]);
		dp1[i][1]=max(a[i],a[i]+dp1[i-1][1]);
	}
	dp2[n-1][0]=a[n-1];
	dp2[n-1][1]=a[n-1];
	for(i=n-2;i>=0;i--)
	{
		dp2[i][0]=min(a[i],a[i]+dp2[i+1][0]);
		dp2[i][1]=max(a[i],a[i]+dp2[i+1][1]);
	}
	int ans=0,p,q,r,s;
	for(i=0;i<n-1;i++)
	{
		p=abs(dp1[i][0]-dp2[i+1][0]);
		p=max(p,abs(dp1[i][1]-dp2[i+1][0]));
		p=max(p,abs(dp1[i][0]-dp2[i+1][1]));
		p=max(p,abs(dp1[i][1]-dp2[i+1][1]));
		if(p>ans)
		{
			q=i;ans=p;
		}
	}
	cout<<q<<" "<<ans<<"\n";
	return 0;

The solution is similar to "Best Time to Buy and Sell Stock III" in leetcode.

MaxLR[] = maximum subarray sum at each position of the input array going left to right. O(n)
MinLR[] = minimum subarray sum at each position of the input array going left to right. O(n)
MaxRL[] = maximum subarray sum at each position of the input array going right to left. O(n)
MinRL[] = minimum subarray sum at each position of the input array going right to left. O(n)
Then for each position i, get the currentMaxdifference by getting the greatest difference between the maximum left-to-right at pos i and the minimum right-to-left at position i+1 (MaxLR[i]-MinRL[i+1]), and the minimum left-to-right at pos i and the maximum right-to-left at pos i+1 (MaxRL[i+1]-MinLR[i]). If the current max diff is greater than the general MaxDiff change maxDiff to currentMaxDiff.

Here is the code that implement this solution, you can use genArray to generate a random array and printArray to print it.

public class DisjointSubarraysDifference {
	public static int maxDiffSubArrays(int[] a) {
		// Compute max left -> right
		int[] maxlr = new int[a.length];
		maxlr[0] = a[0];
		for(int i=1;i<a.length;i++) {
			maxlr[i] = (maxlr[i-1]+a[i]>a[i])?maxlr[i-1]+a[i]:a[i];
		}
		// Compute min left -> right
		int[] minlr = new int[a.length];
		minlr[0] = a[0];
		for(int i=1;i<a.length;i++) {
			minlr[i] = (minlr[i-1]+a[i]<a[i])?minlr[i-1]+a[i]:a[i];
		}
		// Compute max right -> left
		int[] maxrl = new int[a.length];
		maxrl[a.length-1] = a[a.length-1];
		for(int i=a.length-2;i>=0;i--) {
			maxrl[i] = (maxrl[i+1]+a[i]>a[i])?maxrl[i+1]+a[i]:a[i];
		}
		// Compute min right -> left
		int[] minrl = new int[a.length];
		minrl[a.length-1] = a[a.length-1];
		for(int i = a.length-2;i>=0;i--) {
			minrl[i] = (minrl[i+1]+a[i]<a[i])?minrl[i+1]+a[i]:a[i];
		}
		int maxDiff = 0;
		int currDiff = 0;
		for(int i=0;i<a.length-1;i++) {
			currDiff = Math.max((maxlr[i]-minrl[i+1]),(maxrl[i+1]-minlr[i]));
			if(currDiff>maxDiff) {
				//System.out.println("New Breaking Point: "+i);
				maxDiff=currDiff;
			}
		}
		return maxDiff;
	}
	public static int[] genArray(int n) {
		Random r = new Random();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = r.nextInt(10)-4;
		}
		return a;
	}
	public static void printArray(int[] a) {
		for(int i=0;i<a.length-1;i++) {
			System.out.print(a[i]+",");
		}
		System.out.println(a[a.length-1]);
	}
	public static void main(String[] args) {
		int[] a = genArray(10);
		printArray(a);
		int maxDiff = maxDiffSubArrays(a);
		System.out.println("MaxDiff "+maxDiff);
	}
}

public class CareerCup_19286747{
        public static void main(String[]args){
                int[][] arrs = new int[][]{
                        {2,-1,-2,12,453,-9,2,8}
                        ,{7,-1,4}
                        ,{1,2,3,4,5}
                        ,{-1,-3,-5,-2,-1,-4}
                        ,{2, -1, -2, 1, -4, 2, 8}
                };
                for(int[] arr : arrs){
                        Range[] ranges = findRanges(arr);
                        print(arr, ranges[0], ranges[1]);
                }
        }
        static Range[] findRanges(int[] arr){
                Range[] minSumsFromLeft = findMinSumsFromLeft(arr);
                Range[] maxSumsFromRight = findMaxSumsFromRight(arr);
                int i = findOptimalSplit(minSumsFromLeft, maxSumsFromRight);

                Range[] maxSumsFromLeft = findMaxSumsFromLeft(arr);
                Range[] minSumsFromRight = findMinSumsFromRight(arr);
                int j = findOptimalSplit(maxSumsFromLeft, minSumsFromRight);

                int diff1 = optimalValAtSplit(i, minSumsFromLeft, maxSumsFromRight);
                int diff2 = optimalValAtSplit(j, maxSumsFromLeft, minSumsFromRight);
                if (diff1 > diff2){
                        return optimalRangesAtSplit(i, minSumsFromLeft, maxSumsFromRight);
                } else {
                        return optimalRangesAtSplit(j, maxSumsFromLeft, minSumsFromRight);
                }
        }
        static Range[] optimalRangesAtSplit(int i, Range[] leftSums, Range[] rightSums){
                return new Range[]{leftSums[i], rightSums[i+1] };
        }
        static int optimalValAtSplit(int i, Range[] leftSums, Range[] rightSums){
                return Math.abs(rightSums[i+1].sum - leftSums[i].sum);

        }
        static int findOptimalSplit(Range[] leftSums, Range[] rightSums){
                int maxVal = Integer.MIN_VALUE;
                int ans = -1;
                for(int i = 0; i < leftSums.length; ++i){
                        int nextVal = optimalValAtSplit(i, leftSums, rightSums);
                        if (maxVal < nextVal){
                                maxVal = nextVal;
                                ans = i;
                        }
                }
                return ans;
        }
        static Comparator<Integer> NATURAL_ORDER = new Comparator<Integer>(){
                public int compare(Integer a, Integer b){
                        return Integer.compare(a,b);
                }
        };
        static Comparator<Integer> REVERSED_ORDER = Collections.reverseOrder(NATURAL_ORDER);
        static Range[] findMinSumsFromLeft(int[] arr){
                return findSumsFromLeft(arr, REVERSED_ORDER);
        }
        static Range[] findMaxSumsFromLeft(int[] arr){
                return findSumsFromLeft(arr, NATURAL_ORDER);
        }
        static Range[] findSumsFromLeft(int[] arr, Comparator<Integer> comparator){
                Range[] ans = new Range[arr.length-1];
                for(int i = 0, s = i, sum = 0; i < ans.length; ++i){
                        sum += arr[i];
                        if (comparator.compare(arr[i], sum)<0){
                                sum = arr[i];
                                s = i;
                        }
                        ans[i] = new Range(s, i, sum);
                }
                return ans;
        }
        static Range[] findMinSumsFromRight(int[] arr){
                return findSumsFromRight(arr, REVERSED_ORDER);
        }
        static Range[] findMaxSumsFromRight(int[] arr){
                return findSumsFromRight(arr, NATURAL_ORDER);
        }
        static Range[] findSumsFromRight(int[] arr, Comparator<Integer> comparator){
                Range[] ans = new Range[arr.length];
                for(int i = arr.length-1, e = i, sum = 0; i > 0; --i){
                        if (comparator.compare(arr[i], sum)<0){
                                sum = arr[i];
                                e = i;
                        }
                        ans[i] = new Range(i, e, sum);
                }
                return ans;
        }
        static void print(int[] arr, Range left, Range right){
                print(arr, left);
                System.out.print(" ");
                print(arr, right);
                System.out.println();
        }
        static void print(int[] arr, Range r){
                System.out.print("[");
                System.out.print(arr[r.start]);
                for(int i = r.start+1; i <= r.end; ++i){
                        System.out.printf(", %d", arr[i]);
                }
                System.out.print("]");
        }
}
class Range{
        int start, end, sum;
        Range(int start, int end, int sum){
                this.start = start;
                this.end = end;
                this.sum = sum;
        }
        public String toString(){
                return String.format("[%d,%d] sum:%d", start, end, sum);
        }
}

Python code

import sys
from math import fabs
input = [2, -1, -2, 1, -4, 2, 8]
n = len(input)

start = 0
maxSum = -sys.maxsize - 1
firstArray = []
secondArray = []

while start < n - 1:
    subLength = 1
    while (start + subLength) < n:
        first = input[start:(start + subLength)]
        second = input[(start + subLength):]
        subLength += 1

        firstSum = 0
        for element in first:
            firstSum += element

        secondSum = 0
        for element in second:
            secondSum += element
        if fabs(firstSum - secondSum) > maxSum:
            maxSum = fabs(secondSum - firstSum)
            firstArray = first
            secondArray = second
    start += 1

print(firstArray, secondArray)

public class MaxDiff {
	public static int computeMaxDiff(int[] arg) {
		int[] maxForward = helper(arg, true, true);
		int[] minForward = helper(arg, false, true);
		int[] maxReverse = helper(arg, true, false);
		int[] minReverse = helper(arg, false, false);
		int result = Math.max(Math.abs(minReverse[0]), Math.abs(maxReverse[0]));
		for(int i = 1; i < arg.length - 1; i++) {
			int current = Math.max(Math.abs(maxForward[i] - minReverse[i + 1]), Math.abs(minForward[i] - maxReverse[i + 1]));
			result = Math.max(result, current);
		}
		return result;
    }
	
	public static int[] helper(int[] arg, boolean isMax, boolean isForward) {
		
		int[] result = new int[arg.length];
		int[] current = new int[arg.length];
		
		if(isMax && isForward) {
			current[0] = arg[0];
			result[0] = Math.max(0, current[0]);
			for(int i = 1; i < arg.length; i++) {
				current[i] = Math.max(current[i - 1] + arg[i], arg[i]);
				result[i] = Math.max(result[i - 1], current[i]);
			}
		} else if(!isMax && isForward) {
			current[0] = arg[0];
			result[0] = Math.min(0, current[0]);
			for(int i = 1; i < arg.length; i++) {
				current[i] = Math.min(current[i - 1] + arg[i], arg[i]);
				result[i] = Math.min(result[i - 1], current[i]);
			}
		} else if(isMax && !isForward) {
			current[arg.length - 1] = arg[arg.length - 1];
			result[arg.length - 1] = Math.max(0, current[arg.length - 1]);
			for(int i = arg.length - 2; i > -1; i--) {
				current[i] = Math.max(current[i + 1] + arg[i], arg[i]);
				result[i] = Math.max(result[i + 1], current[i]);
			}
		} else {
			current[arg.length - 1] = arg[arg.length - 1];
			result[arg.length - 1] = Math.min(0, current[arg.length - 1]);
			for(int i = arg.length - 2; i > -1; i--) {
				current[i] = Math.min(current[i + 1] + arg[i], arg[i]);
				result[i] = Math.min(result[i + 1], current[i]);
			}
		}
		return result;
	}
	
}

//O(N) time, O(N) space. Works for the [4,-1,7] case giving a result of 8 and for the case //mentioned in the post giving a result of 16.

public class MaxDiffSvc
{

	public static int findMaxDiff(int[] arr)throws NullPointerException
	{
		if(arr==null)
		{
			throw new NullPointerException();
		}
		int maxDiff=Integer.MIN_VALUE();
		int[][] cache=new int[3][arr.length];
		cache[0][0]=arr[0];//Max sum subarray seen so far
		cache[1][0]=arr[0];//Min sum subarray seen so far
		cache[2][0]=arr[0];//Cumulative sum seen so far
		int minCumSum=0;//Index of minimum cumulative sum seen so far.
		int maxCumSum=0;//Index of Maximum cumulative sum seen so far.
		
		for(int i=1;i<arr.length;i++)
		{
			cache[2][i]=cache[2][i-1]+arr[i];
			int c=cache[2][i];
			int currMax=c-cache[2][minCumSum];//Maximum sum subarray with the element at i.
			int currMin=c-cache[2][maxCumSum];//Minimum sum subarray with the element at i
			//Take the current maximum and subtract the minimum sum subarray upto the index containing the minimum cumulative sum(update maxDiff if needed)
			maxDiff=Math.max(maxDiff,Math.abs(currMax-cache[1][minCumSum]));
			//Take the current minimum and subtract the maximum sum subarray upto the index containing the maximum cumulative sum(update maxDiff if needd)
			maxDiff=Math.max(maxDiff,Math.abs(cache[0][maxCumSum]-currMin));
			
			//Update the maximum and minimum sum subarray known to this point
			cache[0][i]=Math.max(cache[0][i-1],currMax);
			cache[1][i]=Math.min(cache[1][i-1],currMin);
			
			//Update the maximum and minimum cumulative sums known to this point
			minCumSum=c<cache[2][minCumSum]?i:minCumSum;
			maxCumSum=c>cache[2][maxCumSum]?i:maxCumSum;
			
			
		}
		return maxDiff;
	}
}

This is DP problem to find minimum sub array and maximum sub array in the given array.

I think the solution for this array [2,-1,-2,1,-4,2,8] is simply finding minimum sub array and maximum sub array in the given array.

Maximum sub array and minimum sub array can be calculated in single sweep by below formula:

#global variable: maxValue & minValue (whenever min or max value if found update this.)

imaxSum= max (ithSum, ithvalue) & iminSum = min(ithSum, ithValue)

I cannot think of any use case where in max sub sequence array will overlap min sub sequence array.

The algorithm is so simple. Calculate the sum and find the split point where both ends has the biggest difference.

int maxDiff(int[] nums) {
        
        int total = 0;
        for (int i = 0;i < nums.length;i++) {
            total += nums[i];
        }
    
        int bestDiff = 0, subTotal = 0;
        for (int i = 0;i < nums.length;i++) {
            subTotal += nums[i];
			
			// total = sub + remain
            int diff = Math.abs(subTotal - total) + Math.abs(total - subTotal - total);
            if (diff > bestDiff) {
                bestDiff = diff;
            }
        }
        
        return bestDiff;
    }

public static int maxSubArrayDifference(int[] arr) {
    if (arr == null || arr.length < 2) return 0;

    int[] minSumAtIdx = minSubArray(arr, false);
    int[] minSumReverseAtIdx = minSubArray(arr, true);
    int[] maxSumAtIdx = maxSubArray(arr, false);
    int[] maxSumReverseAtIdx = maxSubArray(arr, true);

    int diff = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        int diff1 = Math.abs(maxSumAtIdx[i] - minSumReverseAtIdx[i + 1]);
        diff = Math.max(diff, diff1);

        int diff2 = Math.abs(maxSumReverseAtIdx[i + 1] - minSumAtIdx[i]);
        diff = Math.max(diff, diff2);
    }

    return diff;
}

public static int[] minSubArray(int[] arr, boolean reverse) {
    if (arr == null || arr.length == 0) return null;

    int n = arr.length;
    int[] minAtIdx = new int[n];

    if (reverse) {
        int minSoFar = arr[n - 1];
        int min = arr[n - 1];
        minAtIdx[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            minSoFar = Math.min(arr[i], arr[i] + minSoFar);
            min = Math.min(min, minSoFar);
            minAtIdx[i] = min;
        }
    } else {
        int minSoFar = arr[0];
        int min = arr[0];
        minAtIdx[0] = arr[0];

        for (int i = 1; i < n; i++) {
            minSoFar = Math.min(arr[i], arr[i] + minSoFar);
            min = Math.min(min, minSoFar);
            minAtIdx[i] = min;
        }
    }

    return minAtIdx;
}

public static int[] maxSubArray(int[] arr, boolean reverse) {
    if (arr == null || arr.length == 0) return null;

    int n = arr.length;
    int[] maxAtIdx = new int[n];

    if (reverse) {
        int maxSoFar = arr[n - 1];
        int max = arr[n - 1];
        maxAtIdx[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            maxSoFar = Math.max(arr[i], arr[i] + maxSoFar);
            max = Math.max(max, maxSoFar);
            maxAtIdx[i] = maxSoFar;
        }
    } else {
        int maxSoFar = arr[0];
        int max = arr[0];
        maxAtIdx[0] = arr[0];

        for (int i = 1; i < n; i++) {
            maxSoFar = Math.max(arr[i], arr[i] + maxSoFar);
            max = Math.max(max, maxSoFar);
            maxAtIdx[i] = maxSoFar;
        }
    }

    return maxAtIdx;
}

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

void findDisjointSubArraysWithMaxDiff() {
vector<int> input = {2, -1, -2, 1, -4, 2, 8};

unsigned size = (unsigned)input.size();

// Left to right find min/max subarrays ending at each index.
vector<MinMax> leftMinValues(size), leftMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> leftMinValuesUpto(size), leftMaxValuesUpto(size);

int minSoFar = 1;
int maxSoFar = -1;
leftMinValuesUpto[0] = {INT_MAX, 0, 0};
leftMinValuesUpto[0] = {INT_MIN, 0, 0};
for(int i=0; i< size; ++i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
leftMinValues[i] = {input[i], i, i};
} else {
leftMinValues[i] = {input[i]+minSoFar, leftMinValues[i-1].start, i};
}
minSoFar = leftMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
leftMaxValues[i] = {input[i], i, i};
} else {
leftMaxValues[i] = {input[i]+maxSoFar, leftMaxValues[i-1].start, i};
}
maxSoFar = leftMaxValues[i].value;


if (i == 0) {
leftMinValuesUpto[0] = leftMinValues[0];
leftMaxValuesUpto[0] = leftMaxValues[0];
} else {
leftMinValuesUpto[i] = leftMinValues[i].value < leftMinValuesUpto[i-1].value ? leftMinValues[i] : leftMinValuesUpto[i-1];
leftMaxValuesUpto[i] = leftMaxValues[i].value > leftMaxValuesUpto[i-1].value ? leftMaxValues[i] : leftMaxValuesUpto[i-1];
}
}

// RIGHT VALUES
// Left to right find min/max subarrays ending at each index.
vector<MinMax> rightMinValues(size), rightMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> rightMinValuesUpto(size), rightMaxValuesUpto(size);

minSoFar = 1;
maxSoFar = -1;
rightMinValuesUpto[0] = {INT_MAX, (int)(size-1), (int)(size-1)};
rightMinValuesUpto[0] = {INT_MIN, (int)(size-1), (int)(size-1)};
for(int i=size-1; i >=0; --i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
rightMinValues[i] = {input[i], i, i};
} else {
rightMinValues[i] = {input[i]+minSoFar, i, rightMinValues[i+1].end};
}
minSoFar = rightMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
rightMaxValues[i] = {input[i], i, i};
} else {
rightMaxValues[i] = {input[i]+maxSoFar, i, rightMaxValues[i+1].end};
}
maxSoFar = rightMaxValues[i].value;


if (i == 0) {
rightMinValuesUpto[0] = rightMinValues[0];
rightMaxValuesUpto[0] = rightMaxValues[0];
} else {
rightMinValuesUpto[i] = rightMinValues[i].value < rightMinValuesUpto[i-1].value ? rightMinValues[i] : rightMinValuesUpto[i-1];
rightMaxValuesUpto[i] = rightMaxValues[i].value > rightMaxValuesUpto[i-1].value ? rightMaxValues[i] : rightMaxValuesUpto[i-1];
}
//printf("\n MIN value: %d start: %d end: %d", rightMinValuesUpto[i].value, rightMinValuesUpto[i].start, rightMinValuesUpto[i].end);
//printf("\n MAX value: %d start: %d end: %d", rightMaxValuesUpto[i].value, rightMaxValuesUpto[i].start, rightMaxValuesUpto[i].end);
}

int range = INT_MIN;
MinMax one, two;
int splitAt;
for(int i=0; i<size-1; ++i) {
int range1 = rightMaxValuesUpto[i+1].value - leftMinValuesUpto[i].value;
int range2 = leftMaxValuesUpto[i].value - rightMinValuesUpto[i+1].value;
if (range1 > range2) {
if (range1 > range) {
range = range1;
one = leftMinValuesUpto[i];
two = rightMaxValuesUpto[i+1];
splitAt = i;
}
} else {
if (range2 > range) {
range = range2;
one = leftMaxValuesUpto[i];
two = rightMinValuesUpto[i+1];
splitAt = i;
}
}
}

printf("\n First SubArray: value: %d indexRange [%d: %d] \n Second SubArray: value: %d indexRange [%d: %d] \n splitAt: %d", one.value, one.start, one.end, two.value, two.start, two.end, splitAt);

}

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

void findDisjointSubArraysWithMaxDiff() {
    
    
    vector<int> input = {2, -1, -2, 1, -4, 2, 8};
    
    unsigned size = (unsigned)input.size();
  
    // Left to right find min/max subarrays ending at each index.
    vector<MinMax> leftMinValues(size), leftMaxValues(size);
    
    // min/max values from 0 to to upto current index (avove are ending at current index)
    vector<MinMax> leftMinValuesUpto(size), leftMaxValuesUpto(size);
    
    int minSoFar = 1;
    int maxSoFar = -1;
    leftMinValuesUpto[0] = {INT_MAX, 0, 0};
    leftMinValuesUpto[0] = {INT_MIN, 0, 0};
    for(int i=0; i< size; ++i) {
//cout<<"\n\n i: %d ";
        if(input[i] < input[i]+minSoFar) {
            leftMinValues[i] = {input[i], i, i};
        } else {
            leftMinValues[i] = {input[i]+minSoFar, leftMinValues[i-1].start, i};
        }
        minSoFar = leftMinValues[i].value;
        
        if(input[i] > maxSoFar+input[i]) {
            leftMaxValues[i] = {input[i], i, i};
        } else {
            leftMaxValues[i] = {input[i]+maxSoFar, leftMaxValues[i-1].start, i};
        }
        maxSoFar = leftMaxValues[i].value;
        
        
        if (i == 0) {
            leftMinValuesUpto[0] = leftMinValues[0];
            leftMaxValuesUpto[0] = leftMaxValues[0];
        } else {
            leftMinValuesUpto[i] = leftMinValues[i].value < leftMinValuesUpto[i-1].value ? leftMinValues[i] : leftMinValuesUpto[i-1];
            leftMaxValuesUpto[i] = leftMaxValues[i].value > leftMaxValuesUpto[i-1].value ? leftMaxValues[i] : leftMaxValuesUpto[i-1];
        }
    }
    
    // RIGHT VALUES
    // Left to right find min/max subarrays ending at each index.
    vector<MinMax> rightMinValues(size), rightMaxValues(size);
    
    // min/max values from 0 to to upto current index (avove are ending at current index)
    vector<MinMax> rightMinValuesUpto(size), rightMaxValuesUpto(size);
    
    minSoFar = 1;
    maxSoFar = -1;
    rightMinValuesUpto[0] = {INT_MAX, (int)(size-1), (int)(size-1)};
    rightMinValuesUpto[0] = {INT_MIN, (int)(size-1), (int)(size-1)};
    for(int i=size-1; i >=0; --i) {
//cout<<"\n\n i: %d ";
        if(input[i] < input[i]+minSoFar) {
            rightMinValues[i] = {input[i], i, i};
        } else {
            rightMinValues[i] = {input[i]+minSoFar, i, rightMinValues[i+1].end};
        }
        minSoFar = rightMinValues[i].value;
        
        if(input[i] > maxSoFar+input[i]) {
            rightMaxValues[i] = {input[i], i, i};
        } else {
            rightMaxValues[i] = {input[i]+maxSoFar, i, rightMaxValues[i+1].end};
        }
        maxSoFar = rightMaxValues[i].value;
        
        
        if (i == 0) {
            rightMinValuesUpto[0] = rightMinValues[0];
            rightMaxValuesUpto[0] = rightMaxValues[0];
        } else {
            rightMinValuesUpto[i] = rightMinValues[i].value < rightMinValuesUpto[i-1].value ? rightMinValues[i] : rightMinValuesUpto[i-1];
            rightMaxValuesUpto[i] = rightMaxValues[i].value > rightMaxValuesUpto[i-1].value ? rightMaxValues[i] : rightMaxValuesUpto[i-1];
        }
    //printf("\n MIN value: %d start: %d end: %d", rightMinValuesUpto[i].value, rightMinValuesUpto[i].start, rightMinValuesUpto[i].end);
    //printf("\n MAX value: %d start: %d end: %d", rightMaxValuesUpto[i].value, rightMaxValuesUpto[i].start, rightMaxValuesUpto[i].end);
    }
    
    int range = INT_MIN;
    MinMax one, two;
    int splitAt;
    for(int i=0; i<size-1; ++i) {
        int range1 = rightMaxValuesUpto[i+1].value - leftMinValuesUpto[i].value;
        int range2 = leftMaxValuesUpto[i].value - rightMinValuesUpto[i+1].value;
        if (range1 > range2) {
            if (range1 > range) {
                range = range1;
                one = leftMinValuesUpto[i];
                two = rightMaxValuesUpto[i+1];
                splitAt = i;
            }
        } else {
            if (range2 > range) {
                range = range2;
                one = leftMaxValuesUpto[i];
                two = rightMinValuesUpto[i+1];
                splitAt = i;
            }
        }
    }
    
    printf("\n  First SubArray: value: %d  indexRange [%d: %d] \n Second SubArray: value: %d  indexRange [%d: %d] \n   splitAt: %d", one.value, one.start, one.end, two.value, two.start, two.end, splitAt);
    
}

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

void findDisjointSubArraysWithMaxDiff() {
    
    
    vector<int> input = {2, -1, -2, 1, -4, 2, 8};
    
    unsigned size = (unsigned)input.size();
  
    // Left to right find min/max subarrays ending at each index.
    vector<MinMax> leftMinValues(size), leftMaxValues(size);
    
    // min/max values from 0 to to upto current index (avove are ending at current index)
    vector<MinMax> leftMinValuesUpto(size), leftMaxValuesUpto(size);
    
    int minSoFar = 1;
    int maxSoFar = -1;
    leftMinValuesUpto[0] = {INT_MAX, 0, 0};
    leftMinValuesUpto[0] = {INT_MIN, 0, 0};
    for(int i=0; i< size; ++i) {
//cout<<"\n\n i: %d ";
        if(input[i] < input[i]+minSoFar) {
            leftMinValues[i] = {input[i], i, i};
        } else {
            leftMinValues[i] = {input[i]+minSoFar, leftMinValues[i-1].start, i};
        }
        minSoFar = leftMinValues[i].value;
        
        if(input[i] > maxSoFar+input[i]) {
            leftMaxValues[i] = {input[i], i, i};
        } else {
            leftMaxValues[i] = {input[i]+maxSoFar, leftMaxValues[i-1].start, i};
        }
        maxSoFar = leftMaxValues[i].value;
        
        
        if (i == 0) {
            leftMinValuesUpto[0] = leftMinValues[0];
            leftMaxValuesUpto[0] = leftMaxValues[0];
        } else {
            leftMinValuesUpto[i] = leftMinValues[i].value < leftMinValuesUpto[i-1].value ? leftMinValues[i] : leftMinValuesUpto[i-1];
            leftMaxValuesUpto[i] = leftMaxValues[i].value > leftMaxValuesUpto[i-1].value ? leftMaxValues[i] : leftMaxValuesUpto[i-1];
        }
    }
    
    // RIGHT VALUES
    // Left to right find min/max subarrays ending at each index.
    vector<MinMax> rightMinValues(size), rightMaxValues(size);
    
    // min/max values from 0 to to upto current index (avove are ending at current index)
    vector<MinMax> rightMinValuesUpto(size), rightMaxValuesUpto(size);
    
    minSoFar = 1;
    maxSoFar = -1;
    rightMinValuesUpto[0] = {INT_MAX, (int)(size-1), (int)(size-1)};
    rightMinValuesUpto[0] = {INT_MIN, (int)(size-1), (int)(size-1)};
    for(int i=size-1; i >=0; --i) {
//cout<<"\n\n i: %d ";
        if(input[i] < input[i]+minSoFar) {
            rightMinValues[i] = {input[i], i, i};
        } else {
            rightMinValues[i] = {input[i]+minSoFar, i, rightMinValues[i+1].end};
        }
        minSoFar = rightMinValues[i].value;
        
        if(input[i] > maxSoFar+input[i]) {
            rightMaxValues[i] = {input[i], i, i};
        } else {
            rightMaxValues[i] = {input[i]+maxSoFar, i, rightMaxValues[i+1].end};
        }
        maxSoFar = rightMaxValues[i].value;
        
        
        if (i == 0) {
            rightMinValuesUpto[0] = rightMinValues[0];
            rightMaxValuesUpto[0] = rightMaxValues[0];
        } else {
            rightMinValuesUpto[i] = rightMinValues[i].value < rightMinValuesUpto[i-1].value ? rightMinValues[i] : rightMinValuesUpto[i-1];
            rightMaxValuesUpto[i] = rightMaxValues[i].value > rightMaxValuesUpto[i-1].value ? rightMaxValues[i] : rightMaxValuesUpto[i-1];
        }
    //printf("\n MIN value: %d start: %d end: %d", rightMinValuesUpto[i].value, rightMinValuesUpto[i].start, rightMinValuesUpto[i].end);
    //printf("\n MAX value: %d start: %d end: %d", rightMaxValuesUpto[i].value, rightMaxValuesUpto[i].start, rightMaxValuesUpto[i].end);
    }
    
    int range = INT_MIN;
    MinMax one, two;
    int splitAt;
    for(int i=0; i<size-1; ++i) {
        int range1 = rightMaxValuesUpto[i+1].value - leftMinValuesUpto[i].value;
        int range2 = leftMaxValuesUpto[i].value - rightMinValuesUpto[i+1].value;
        if (range1 > range2) {
            if (range1 > range) {
                range = range1;
                one = leftMinValuesUpto[i];
                two = rightMaxValuesUpto[i+1];
                splitAt = i;
            }
        } else {
            if (range2 > range) {
                range = range2;
                one = leftMaxValuesUpto[i];
                two = rightMinValuesUpto[i+1];
                splitAt = i;
            }
        }
    }
    
    printf("\n  First SubArray: value: %d  indexRange [%d: %d] \n Second SubArray: value: %d  indexRange [%d: %d] \n   splitAt: %d", one.value, one.start, one.end, two.value, two.start, two.end, splitAt);
    
}

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

Here's what I came up with in Javascript using tabulation. The time complexity should be O(4n) which simplifies to O(n).

It ends up doing 4 loops (hence the 4n), and everything else inside and outside the loops is static (accessing/assigning elements in an array and comparing 2 numbers).

function maxDiffContiguousArrs2(arr) {

    function helper(cb1, cb2) {
        let l2rTab = new Array(arr.length - 1);
        let r2lTab = new Array(arr.length - 1);

        let tabLen = r2lTab.length;

        l2rTab[0] = arr[0];
        r2lTab[tabLen - 1] = arr[arr.length - 1];

        
        for (let i = 1; i < tabLen; i++) {
            l2rTab[i] = cb1((arr[i] + l2rTab[i - 1]), arr[i])
            r2lTab[tabLen - i - 1] = cb2((arr[arr.length - 1 - i] + r2lTab[tabLen - i]), arr[arr.length - 1 - i]);
        }

        let maxDiff = -Infinity

        for (let i = 0; i < tabLen; i++) {
            maxDiff = Math.max(Math.abs(l2rTab[i] - r2lTab[i]), maxDiff)
        }
        return maxDiff
    }
    return Math.max(helper(Math.min, Math.max), helper(Math.max, Math.min))
}

Is the exhaustive algo O(2^n * n) where n is # of digits in original set? Thats because you could make 2^n different pairs of subsets, and for each pair, you do sums of O(n).

I wonder if you could sort the origianal set and then walk up the sorted list, splitting it at each of the N points (forming the two subsets) and computing the difference of each of these subsets at each step, looking for the max? If so, you could optimize the sum, as you are just adding one new value to the sum of the first and removing it from the sum of the second.

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

The easiest solution posted ever, I wonder why people solve it so hard, just compute the sum of all elements, go through the array, compute the sum of first part=>second part, and compare :

int findMaxDiff(vector<int>& array) {
	int sum=0;
	for(int i=0; i<array.size(); ++i) {
		sum+=array[i];
	}
	int sum1=0;
	int max_diff=INT_MIN;
	for(int i=0; i<array.size(); ++i) {
		sum1+=array[i];
		int diff=fabs((sum-sum1)-sum1);
		if(diff>max_diff) max_diff=diff;
	}
	return max_diff;
}

easiet solution ever, wonder why people have written lines of code for this question:

int findMaxDiff(vector<int>& array) {
	int sum=0;
	for(int i=0; i<array.size(); ++i) {
		sum+=array[i];
	}
	int sum1=0;
	int max_diff=INT_MIN;
	for(int i=0; i<array.size(); ++i) {
		sum1+=array[i];
		int diff=fabs((sum-sum1)-sum1);
		if(diff>max_diff) max_diff=diff;
	}
	return max_diff;
}

This problem can be divided into 2 subproblems:
1. Find a subset whose sum is maximum, it is O(n) algorithm
2. Find a subset whote sum in min, it is O(n) algorithm.
3. Also verify that solution from step 1 and step 2 dont overlap (they will not). Find the absolute difference between subsets find in steps1 and steps2 and take their absolute difference.

I can be done using kandane. For maximum difference we need to find minimum contiguous sub array and maximum contiguous sub array. Then find the start and end index of both array and make sure they both are not colliding with each other if they are colliding then take maximum difference by including it into minimum subset and maximum subset.

It can be done using kandane. For maximum difference we need to find minimum contiguous sub array and maximum contiguous sub array. Then find the start and end index of both array and make sure they both are not colliding with each other if they are colliding then take maximum difference by including it into minimum subset and maximum subset.