# Best way to split array to two sub-arrays, with maximum absolute difference between them

Given array a, we want to find an index k in range [0, a.length-1] such that:

Math.abs( (a[0]+a[1]+...a[k-1]) - (a[k] + a[k+1] + ... + a[a.length-1]) )


is maximal (in case k == 0, the result above is the sum of a elements).

Below is the code I wrote.

public static int sumArray(int[] a) {
int sum = 0;
int len = a.length;

for (int i = 0; i < len; i++) {
sum += a[i];
}

return sum;
}

public static int findMaxDif(int[] a) {
int left = 0;
int right = sumArray(a);
int max = Math.abs(right);
int maxIndex = 0;
int difI;
int len = a.length - 1;

for (int i = 0; i < len; i++) {
left += a[i];
right -= a[i];
difI = Math.abs(left - right);

if (difI > max) {
max = difI;
maxIndex = i + 1;
}
}

return maxIndex;
}


Simple tests that I wrote and work fine:

public static void main (String[] args) {
int[] a1 = {1,2};
if (findMaxDif(a1) == 0) {
System.out.println("test1 pass");
}

int[] a2 = {-1,2};
if (findMaxDif(a2) == 1) {
System.out.println("test2 pass");
}

int[] a3 = {2,-1};
if (findMaxDif(a3) == 1) {
System.out.println("test3 pass");
}

int[] a4 = {-5,-4,4,3};
if (findMaxDif(a4) == 2) {
System.out.println("test4 pass");
}
}


• You can replace sumArray with IntStream.of(a).sum();.
• shouldPartitionSingleElementListAtStart and shouldPartitionListWithMultipleIdenticalValuesAtStart tests would be useful.
• What happens if the input is an empty list? It's up to you whether that should fail like (I think) it does now, but the case should be tested. You might even want to raise a custom NonPartitionableListException or EmptyListException in this case.
• Variable names should be understandable at the point they are defined - it should not be necessary to see all their usages to understand what they do. So for example left could be called leftPartitionSum.
• On a related note, findMaxDif might be clearer as getMaxPartitionDifferenceIndex. "find" is usually used when you want to return a "non-answer" in case no answer is possible, while "get" is usually used when you want the code to throw an exception if there is no answer.