Mfcttrf

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<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 <=3) 
 int val = 0;
 for (int i=start; i<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<a.length; i++) 
 sum += a[i];
 
 System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
 

A note on efficiency. Currently the code exhibit an exponential time complexity. It can be reduced significantly.

Notice that the same position is inspected more than once. For example, the opening sequences 3, 1, 2, 2 and 1, 3 all lead to the same position. Further down the game the situation aggravates.

Keep track of the positions already inspected, and before diving into the recursion check whether it is still unknown. Since the position is just an integer (an amount of stones remaining), the cost of tracking is $O(n)$ space.

Further improvement is of course alpha-beta pruning.