In the **coin in a line problem**, two players are given an even number of coins in a single row.
The players take turns alternatively. For each turn, a player selects a coin from either the beginning or the end of the row. The player with the maximum total value wins.
​


So, the goal is to provide a strategy in which the player with the first move gets the maximum value coins in the end.


There is an even amount of coins (i.e., 1 to n ) and the two players take their turns alternatively.

If *player1* picks the coin at position 1, then *player2* (who is equally clever) will pick up a coin and leave *player1* with the less valuable coin.


If *player1* picks the coin at position n, then *player2* (who is equally clever) will pick up a coin, and leave *player1​* with the less valuable coin.

# Combined Form

```Python
Max_Value(1,n) = Maximum {coin[1] + Minimum{Max_Value(3,n),
Max_Value(2,n-1)} , coin[n] +
Minimum{Max_Value(2,n-1),Max_Value(1,n-2)}};
```

# Python Implementation
def Coin_in_a_line(arr, n): 
	
	# Creating a table to store max value.
	Max_Value = [[0 for i in range(n)] 
				for i in range(n)] 

    # Fill the table using the above method.
	for k in range(n): 
		for j in range(k, n): 
			i = j - k 
			 
			x = 0
			if((i + 2) <= j): 
				x = Max_Value[i + 2][j] 
			y = 0
			if((i + 1) <= (j - 1)): 
				y = Max_Value[i + 1][j - 1] 
			z = 0
			if(i <= (j - 2)): 
				z = Max_Value[i][j - 2] 
			Max_Value[i][j] = max(arr[i] + min(x, y), 
							arr[j] + min(y, z)) 
	return Max_Value[0][n - 1] 

# Sample code 
arr = [ 5, 16, 3, 7 ]
print(Coin_in_a_line(arr, 4)) 

Python

// Java Implementation
public class main {
  // Class to find the maximum value.
	public static int Coin_in_a_line(int[] arr) {
    // Matrix to store max value. 
		int[][] Max_Value = new int[arr.length][arr.length];

    // Filling the matrix using the above algorithm.
		for (int k = 0; k < arr.length; k++) {
			for (int i = 0, j = k; j < arr.length; i++, j++) {

				int x, y, z;
				if (i + 2 <= j)
					x = Max_Value[i + 2][j];
				else
					x = 0;
				if (i + 1 <= j - 1)
					y = Max_Value[i + 1][j - 1];
				else
					y = 0;
				if (i <= j - 2)
					z = Max_Value[i][j-2];
				else
					z = 0;
				Max_Value[i][j] = Math.max(arr[i] + Math.min(x, y), arr[j]+ Math.min(y, z));
			}
		}
		return Max_Value[0][arr.length - 1];
	}
  // Sample program
	public static void main(String[] arguments) {
		int[] array = { 5, 16, 3, 7 };
		System.out.println(Coin_in_a_line(array));
	}
}

Java

This problem can be solved most efficiently by **dynamic programming**. The main logic behind the code is explained best by the `Max_Value` array:

The row number specifies the starting position and the column number specifies the ending position within the coin line. We must pick a coin at either end of this range. So, `Max_Value[i][j]` would mean the range from `i` to `j`.

In the code, `k` is the interval or window. The base case is when `k` is `0` or `i = j`. This means that there is only one coin to choose. Hence, the diagonal of the array will be filled first:

Next, the interval is `1`, meaning there are `2` choices to pick from, namely `arr[i]` or `arr[j]`. We must pick the maximum between these two. These values are filled out in the array:

Now, the interval is `2` or larger. There are a few possible scenarios we need to cover. At the start, we can pick either `arr[i]` (first) or `arr[j]` (last). 

If we pick the first value, our opponent can choose either `arr[i+1]` or `arr[j]`. 

- If they pick `arr[i+1]`, our next choice will be `arr[i+2]` or `arr[j]`. But since we built up from the base case, we already have the max value for this in `Max_Value[i+2][j]`! We will store this in `x`.
- If they pick `arr[j]`, our next choice will be `arr[i+1]` or `arr[j-1]`. This can be found in `Max_Value[i+1][j-1]`. We will store this in `y`.

So, for this scenario, what we have as our choice of moves is:
```python
arr[i] + min(x, y)
```
If we pick the last value, our opponent can choose either `arr[i]` or `arr[j-1]`. 

- If they pick `arr[i]`, our next choice will be `arr[i+1]` or `arr[j-1]`. This can be found in `Max_Value[i+1][j-1]`. Like before, we will store this in `y`.
- If they pick `arr[j-1]`, our next choice will be `arr[i]` or `arr[j-2]`. This can be found in `Max_Value[i][j-2]`. We will store this in `z`.

So, for this scenario, what we have as our choice of moves is:
```python
arr[j] + min(y, z)
```
Lastly, we must take the maximum out of these two scenarios:
```python
max(arr[i] + min(x, y), arr[j] + min(y, z))
```
This will help us find `Max_Value[0][3]`, which is the answer!



What is the coin in a line problem?

Combined Form

Code