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&lt;cases;i++)
    {
        int size=sc.nextInt();
        int[] array=new int[size];

        for(int j=0;j&lt;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&amp;&amp;start==0&amp;&amp;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&lt;size;i++)
    {
        if(sumOfArray(array,start,start+i)!=sumOfArray(array,start+i+1,end))
        {
            continue;
        }
        else
        {
            count+=1;
            return count+Math.max(splitPossible(array,start,start+i),splitPossible(array,start+i+1,end));
        }
    }

    return count;
}
public static int sumOfArray(int[] array,int start,int end)
//returns sum of array from start to end.
{
    int sum=0;
    for(int j=start;j&lt;=end;j++)
    {
        sum+=array[j];
    }
    return sum;
}
}


I am new to recursion, so any input in designing of recursive method/assigning or simplifying variables/simpler coding styles during recursion are welcomed.
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 &amp;&amp; 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 &amp;&amp; size == array.length) {
        return array.length - 1;
    }
    for (int i = 0; i &lt; 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 (size == 1) {
    return 0;
}


which avoids traversing the array entirely.

Further improvements

It might sound a bit strange to you, as it probably is to new developers, but a lot of APIs, for all programming languages, very often deal with ranges in an open-half manner: when asked for something in the range from start to end, it will generally be implied start inclusive to end exclusive (like Python slice, C++ APIs, and in Java, look at Random.nextInt, IntStream.range, List.subList or String.substring). The current code implies that the end is inclusive, which, actually, makes it that bit harder to follow for those accostumed to those practices. And switching to an exclusive end will make the code even easier:

// start inclusive, end exclusive
public static int getMaxScore(int[] array, int start, int end) {
    for (int i = 1; i &lt; end - start; i++) {
        int split = start + i;
        if (sumOfArray(array, start, split) == sumOfArray(array, split, end)) {
            return 1 + Math.max(getMaxScore(array, start, split), getMaxScore(array, split, end));
        }
    }
    return 0;
}

// start inclusive, end exclusive
public static int sumOfArray(int[] array, int start, int end) {
    int sum = 0;
    for (int j = start; j &lt; end; j++) {
        sum += array[j];
    }
    return sum;
}





There is no need to have special cases for a size of 0 or 1; the code handles them already.
There is a clear split index, which corresponds to where the left and right arrays are split.


All the test cases still pass after making those changes.