# Optimal Strategy Game Pick from Ends of array Dynamic Programming

N pots, each with some number of gold coins, are arranged in a line. You are playing a game against another player. You take turns picking a pot of gold. You may pick a pot from either end of the line, remove the pot, and keep the gold pieces. The player with the most gold at the end wins. Develop a strategy for playing this game.

Optimal Strategy Game Pick from Ends of array Dynamic Programming

```Input : { 3, 9, 1, 2 } Output : 11 ```

```package com.omt.learn.algo;

class Data {

int left = 0;
int right = 0;

public static Data getData(int l, int r) {
Data d = new Data();
d.left = l;
d.right = r;
return d;
}
}

public class OptimalGameProblem {

public static void main(String[] args) {
int a[] = { 3, 9, 1, 2 };
System.out.println(getMaxForPlayerOne(a));
}

public static int getMaxForPlayerOne(int[] a) {

Data[][] matrix = new Data[a.length][a.length];

for (int l = 1; l <= a.length; l++) {

for (int i = 0; i < a.length; i++) {

int j = i + l - 1;
if (j < a.length) {
if (l == 1) {
matrix[i][j] = Data.getData(a[i], 0);
} else {

int leftPick = a[i] + matrix[i + 1][j].right;
int rightPick = a[j] + matrix[i][j - 1].right;

if (leftPick > rightPick) {
matrix[i][j] = Data.getData(leftPick, matrix[i + 1][j].left);
} else {
matrix[i][j] = Data.getData(rightPick, matrix[i][j - 1].left);
}

}
}
}

}

printMatrix(matrix);
return matrix[0][a.length - 1].left;

}

public static void printMatrix(Data[][] matrix) {

for (Data[] datas : matrix) {

for (int i = 0; i < datas.length; i++) {
Data d = datas[i];
if (d == null) {
System.out.print("(--,--) ");
} else {

System.out.print("(" + appendZero(d.left) + "," + appendZero(d.right) + ") ");
}
}
System.out.println();

}

}

public static String appendZero(int v) {
return v < 10 ? "0" + v : v + "";
}

}
```