Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Maximize coin selection to win game

Problem: Given an unsorted array of pots containing coins.
A and B play a game where they take turns and pick up a pot either from the beginning or the end of array.
If A plays first, devise a strategy to help him win the game.

Solution: A recursive solution for this can be as follows:

```
import java.util.*;

public class MaximizeCoinCollection
{

public static void main(String[] args)
{
int numPots = 6;
int[] arr = getRandomCoins(numPots);

System.out.println(findMaxCoins (arr, 0, numPots-1));
}

// The most important part to understand here is why minimum is being chosen from the recursive calls.
// This is so because the recursive calls the best sums A would choose for himself.
// Since B is also playing with full efficiency, he will do his best to minimize the A's profit.
// And so, B will choose a pot which will allow A to choose his next pot with minimum benefit.
// For example: if B has to choose from 2,10,2,4,3, then
// B will never choose 2 as that would expose 10 to A.
// Since B will always offer a minimum to A, we take the minimum from the recursive calls.
//
// But after recursion is done, then A will definitely maximize his profit
// And that is where we choose maximum
static int findMaxCoins(int[] arr, int start, int end)
{
if (start > end)
return 0;

if (start == end)
return arr[start];

int a = arr[start] + Math.min(findMaxCoins(arr, start+2, end), findMaxCoins(arr, start+1, end-1));
int b = arr[end]   + Math.min(findMaxCoins(arr, start+1, end-1), findMaxCoins(arr, start, end-2));

return Math.max(a, b);
}

// Helper method to get random coins in pots
static int[] getRandomCoins(int numPots)
{
int arr[] = new int[numPots];

for (int i=0; i<numPots; i++)
{
arr[i] = 1+(int)(Math.random()*numPots*2.33);
System.out.print (arr[i]+", ");
}

System.out.println();
return arr;
}
}

```

Order analysis: Order of execution for the above code is exponential.
It executes 4 loops in each recursive call and recursion depth is N.
So order is O(4N)

Example executions:
```Coins: 5, 2, 7, 8,
Max Sum for A: 13

Coins: 1, 12, 3, 12, 6, 10,
Max Sum for A: 34

Coins: 2, 8, 10, 12, 13, 3,
Max Sum for A: 25

Coins: 7, 13, 10, 10, 14, 2,
Max Sum for A: 31

```

Printing order of choosing coins:
Above will be more clear if we can also print what coins are being chosen by A.
Such a thing will also help A proceed with the game because just a max-sum is useless for A to actually play the game.

```
import java.util.*;

public class MaximizeCoinCollectionWithSteps
{

public static void main(String[] args)
{
int numPots = 6;
int[] arr = getRandomCoins(numPots);

ArrayList<Integer> l = new ArrayList<Integer> ();
int maxCoins = findMaxCoins (arr, 0, numPots-1, l);
printAns(maxCoins, l);
}

// The most important part to understand here is why minimum is being chosen from the recursive calls.
// This is so because the recursive calls the best sums A would choose for himself.
// Since B is also playing with full efficiency, he will do his best to minimize the A's profit.
// And so, B will choose a pot which will allow A to choose his next pot with minimum benefit.
// For example: if B has to choose from 2,10,2,4,3, then
// B will never choose 2 as that would expose 10 to A.
// Since B will always offer a minimum to A, we take the minimum from the recursive calls.
//
// But after recursion is done, then A will definitely maximize his profit
// And that is where we choose maximum
static int findMaxCoins(int[] arr, int start, int end, ArrayList<Integer> l)
{
if (start > end)
return 0;

if (start == end)
{
return arr[start];
}

ArrayList<Integer> l1 = new ArrayList<Integer> ();
ArrayList<Integer> l2 = new ArrayList<Integer> ();
ArrayList<Integer> l3 = new ArrayList<Integer> ();
ArrayList<Integer> l4 = new ArrayList<Integer> ();

int a = arr[start] + findMaxCoins(arr, start+2, end, l1);
int b = arr[start] + findMaxCoins(arr, start+1, end-1, l2);
int c = arr[end]   + findMaxCoins(arr, start+1, end-1, l3);
int d = arr[end]   + findMaxCoins(arr, start, end-2, l4);

ArrayList<Integer> tmp1;
ArrayList<Integer> tmp2;
int min1;
int min2;

if (a < b)
{
tmp1 = l1;
min1 = a;
}
else
{
tmp1 = l2;
min1 = b;
}

if (c < d)
{
tmp2 = l3;
min2 = c;
}
else
{
tmp2 = l4;
min2 = d;
}

if (min1 > min2)
{
return min1;
}
else
{
return min2;
}
}

// Helper method to print the answer
static void printAns(int maxCoins, ArrayList<Integer> l)
{
System.out.print ("Order of choosing coins: ");
for (int i=l.size()-1; i>=0; i--)
System.out.print (l.get(i) + ", ");
System.out.println("\nMax sum = " + maxCoins);
}

// Helper method to get random coins in pots
static int[] getRandomCoins(int numPots)
{
int arr[] = new int[numPots];

for (int i=0; i<numPots; i++)
{
arr[i] = 1+(int)(Math.random()*numPots*2.33);
System.out.print (arr[i]+", ");
}

System.out.println();
return arr;
}
}

```

Example executions:

```
Pots: 5, 1, 6, 6,
Order of choosing coins: 6, 5,
Max sum = 11

Pots: 7, 12, 9, 11, 10, 13,
Order of choosing coins: 13, 11, 12,
Max sum = 36

Pots: 1, 5, 13, 6, 9, 11,
Order of choosing coins: 11, 1, 13,
Max sum = 25

Pots: 18, 9, 3, 8, 15, 9, 5, 19,
Order of choosing coins: 19, 9, 3, 15,
Max sum = 46

```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: