"What is the maximum that Player 1 can win?" This is a question that I encountered in one of the competitive coding tests. The question goes as follows:


  A 2-player game is being played. There is a single pile of stones. Every stone has an amount (positive) written on top of it. At every turn, a player can take the top 1 or 2 or 3 stones and add to his kitty. Both players want to maximize their winnings. Assuming both players play the game optimally and Player 1 starts the game, what is the maximum amount that Player 1 can win?


I have devised the following recursive approach:

class Main {
  public static void main(String[] args) {
    int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
    int sum = 0;
    for (int i=0;i&lt;a.length; i++) {
      sum += a[i];
    }
    System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
  }
  public static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) {
    if (len-start &lt;=3) {
      int val = 0;
      for (int i=start; i&lt;len; i++) {
        val += a[i];
      }
      return val;
    }

    int v1 = a[start] + (sum - currSum - a[start]) - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = a[start] + a[start+1] + (sum - currSum - a[start] - a[start+1]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = a[start] + a[start+1] + a[start+2] + (sum - currSum - a[start] - a[start+1] - a[start+2]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

    return Math.max(v1, Math.max(v2, v3));
  }
}


I have checked my solution on a few inputs. Is my algorithm correct?
Usability

I have a remark about defining recursive functions. 
You don't want consumers of your API to think about the intermediate variables and their initial value. The consumer does not care you are using recursion internally.

Make your recursive function private.

private static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) 


And create a public API entrypoint.

public static int maxPlayer1(int[] a) {
     final int sum = IntStream.of(a).sum();
     return maxPlayer1(a, 0, sum, 0, a.length);
}


The consumer can now call your API without getting a headache:

public static void main(String[] args) {
     final int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
     System.out.println(maxPlayer1(a));
}


As compared to the original code the consumer had to write.


public static void main(String[] args) {
    int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
    int sum = 0;
    for (int i=0;i&lt;a.length; i++) {
      sum += a[i];
    }
    System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
  }