Repeatedly partitioning an array equally as far as possible

I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases.


Nikita just came up with a new array game. The rules are as follows:



-
Initially, there is an array, A, containing N integers (1 ≤ N ≤ 109), with 0 ≤ Ai ≤ 109.

-
In each move, Nikita must partition the array into 2 non-empty parts
such that the sum of the elements in the left partition is equal to
the sum of the elements in the right partition. If Nikita can make
such a move, she gets 1 point; otherwise, the game ends.

-
After each successful move, Nikita discards either the left partition
or the right partition and continues playing by using the remaining
partition as array A.



Nikita loves this game and wants your help getting the best score
possible. Given A, can you find and print the maximum number of points
she can score?

```
import java.io.*;
import java.util.*;

public class NikitaAndTheGame
{

public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int cases=sc.nextInt();
for(int i=0;i<cases;i++)
{
int size=sc.nextInt();
int[] array=new int[size];

for(int j=0;j<size;j++)
{
array[j]=sc.nextInt();
}

System.out.println(splitPossible(array,0,size-1));

}
}
public static int splitPossible(int[] array,int start,int end)
//a recursive fuction that returns 1 if equal sum split possible otherwise returns 0
{
int size=end-start+1;
int sum=0;
int count=0;
if(sumOfArray(array,0,array.length-1)==0&&start==0&&end==array.length-1) //handles the case when all elements of array are 0.

{
return array.length-1;
}
if(size==0)
{
return 0;
}
for(int i=0;i<size;i++)
{
if(sumOfArray(array,start,start+i)!=sumOfArray(array,start+i+1,end))
{
continue;
}
else
{
count+=1;
return count+Math.max(splitPossible(

The implementation of the algorithm, using a helper recursive method, is very clear. It is easy to see what the code is doing:

• There are 2 base cases: there are only 0s, in which case the size of the array is the score, and the size is zero, in which case the score is 0.

• Then, for all possible sizes, we keep the maximum of the score of the left array versus the right array when they have equal sum, adding 1.

There are simplifications possible, and improvements in terms of style and namings.

Namings

The first point to consider is naming: splitPossible is a terrible name for this method. It doesn't convey what it's doing. Rename it to getMaxScore, since this is what it does: gets the maximum score for the given array in the given bounds.

Also, consider "hiding" the recursive implementation inside a new method by creating a method passing the initial values:

public static int getMaxScore(int[] array) {
    return getMaxScore(array, 0, array.length - 1);
}

private static int getMaxScore(int[] array, int start, int end) {
    // rest of code
}

This way, the caller just needs to invoke getMaxScore(array), without worrying about the initial value of the recursive algorithm; and it gives you the possibility to update the code in the future (to an iterative method for example) without changing the calling code.

Style

You should always reformat your code in order to have proper indentation. Right now, it isn't the case and makes the code harder to read for no reason.

int sum = 0;

is unused in the program, so you should remove it.

if (sumOfArray(array, start, start + i) != sumOfArray(array, start + i + 1, end)) {
  continue;
} else {
  count += 1;
  return count + Math.max(getMaxScore(array, start, start + i), getMaxScore(array, start + i + 1, end));
}

is the logic for the recursive calls. In this case, there is no need to use a continue statement: those can sometimes help understanding the logic when there would be a lot of code in the else branch. They introduce a sort of early-return inside the for loop. But in this case, it clutters up a bit, and you can simply have:

if (sumOfArray(array, start, start + i) == sumOfArray(array, start + i + 1, end)) {
    count += 1;
    return count + Math.max(getMaxScore(array, start, start + i), getMaxScore(array, start + i + 1, end));
}

A couple of more comments here: count += 1; is more generally written count++ (or ++count), but in fact, there is no need for this as you can just add 1 to the result of the next line:

return 1 + count + Math.max(getMaxScore(array, start, start + i), getMaxScore(array, start + i + 1, end));

Arguably, this line is starting to become a bit crowded, so it is possible to store the two intermediate recursive results in temporary variables:

int leftScore = getMaxScore(array, start, start + i);
int rightScore = getMaxScore(array, start + i + 1, end);
return 1 + count + Math.max(leftScore, rightScore);

Improvements

You have an early return in case the size is 0, to return 0. While that can make the code easier to follow in certain situations, in this case, it's not needed at the rest of the code handles size = 0 just fine. Actually, the for loop is not entered, and we directly return the count, which is 0. Consider removing this special case (it also doesn't lead to performance improvements).

But why is there a count variable in the first place? It's initialized to 0, and in fact never changes. It's actually really unneeded: when making the recursive call, the total score is always the maximum score of the left and right split, plus 1. You can safely remove this count variable.

The first if, in case the array only contains 0, can be written more simply as well: start == 0 && end == array.length - 1 is equivalent to size == array.length.

The recursive method now looks like:

public static int getMaxScore(int[] array, int start, int end) {
    int size = end - start + 1;
    if (sumOfArray(array, 0, array.length - 1) == 0 && size == array.length) {
        return array.length - 1;
    }
    for (int i = 0; i < size; i++) {
        if (sumOfArray(array, start, start + i) == sumOfArray(array, start + i + 1, end)) {
            int leftScore = getMaxScore(array, start, start + i);
            int rightScore = getMaxScore(array, start + i + 1, end);
            return 1 + Math.max(leftScore, rightScore);
        }
    }
    return 0;
}

Finally, something can be done to simplify this first early-return. When all the elements in the array are 0, the recursive calls inside the for loop handle the case fine as well: they will increment the count by 1 each time, finally ending up with array.length - 1. But we can't get total rid of it: the way the algorithm is build, splitting each array into smaller chunks, the special case is when size == 1, and in this case, it is impossible to split it evenly, so the answer is 0. So we could have

```
if (

StackExchange Code Review Q#146373, answer score: 4