1
\$\begingroup\$

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.
Please tell me your opinion about it - run time, correctness and coding conventions.

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");
    }
}  
\$\endgroup\$
1
\$\begingroup\$

Some ideas:

  • You can replace sumArray with IntStream.of(a).sum();.
  • Tests should be written using JUnit or another testing framework and named according to what they are testing.
  • Try to write the absolutely most simple test case you can think of rather than following the writer's instinct to vary the input. You want the mental arithmetic to verify your test results to be as simple as absolutely possible. Your tests should be easy to rewrite using just -1, 0 and 1.
  • 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.
  • "Difference" is usually spelled out fully or, if shortened, written as "Diff" (two "f"s).
  • 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.

Other than that my opinion is that this code is short, readable and performant.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.