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 + "";
	}

}